Check out the course offered by CMU at

https://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

## 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\)