Check out the course offered by CMU at

## Encoding byte values

• 1 byte = 8 bits
• Range from:
• Binary 00000000 to 11111111
• Decimal 0 to 255
• Hexidecimal 00 to FF

## Boolean algebra

### Relationship with set operation

• And (&) => intersection
A&B = 1 when A = 1 and B = 1
• Or (|) => union
A|B = 1 when either A = 1 or B = 1
• Not (~) => symmetric difference
~A = 1 when A = 0
• Exclusive-or (^) => complement
A^B = 1 when either A = 1 or B = 1, but not both

### Shift operations

• Left shift (x << y): throw away extra bit; fill with 0 on right
• Right shift (x >> y)
Logical shift: fill with 0 on left
Arithmetic shift: replicate MSB (most significant figure)
• Undefined: shift amount < 0 or >= word size

### Integer representation

• Unsigned:
$B2U(X)=\sum_{i=0}^{w-1}x_i\cdot2^i$
e.g. $$1011=1×2^0+1×2^1+0×2^3+1×2^4$$
• Two's complement:
$B2T(X)=-x_{w-1}\cdot2^{w-1}+\sum_{i=0}^{w-2}x_i\cdot2^i$
e.g. $$1011=−1×2^3+(1×2^0+1×2^1+0×2^2 )$$

### Numeric range of integer representations

Unsigned:
$UMin=0=000..0$
$UMax=2^{w−1}= 111..1$

Two's complement
$TMin=−2^{w−1}$
$TMax=2^{w−1}−1$
(p.s. -110 = 111…12 in 2's complement)

$|TMin|=TMax+1$
$UMax=2\times TMax+1$

### Mapping between signed and unsigned

• Keep bit representation and reinterpret
• Large negative becomes large positive
• T2U(x)=x_(w−1)∙2^w+x
• Justification:
$B2U(X)−B2T(X)=x_{w−1}\cdot[2^{w−1}−(−2^{w−1} )]=x_{w−1}\cdot(2\cdot2^{w−1} )=x_{w−1}\cdot2^w$
$B2U(X)=x_{w−1}\cdot2^w+B2T(X)$
If we let B2T(X)=x, then, $$B2U(T2B(x))=T2U=x_{w−1}\cdot2^w+x$$
• In expression containing signed and unsigned, signed is cast to unsigned

### Expanding

To convert w-bit signed integer to w + k bit integer with same value, make k copies of sign bit

• Justification
$X=−2^{w−1} x_{w−1}$
$X^′=−2^{w} x_{w−1}+2^{w−1} x_{w−1}=(−2^w+2^{w−1} ) x_{w−1}$

### Why use unsinged

Don’t use just because number is nonnegative; do use when need extra bit's worth of range

### Truncation (drop the high order w-k bits)

• Unsigned (w-bit to k-bit): $$\mod 2^k$$
• Two's complement (w-bit to k-bit): Cast to unsigned then $$\mod 2^k$$