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 \cdot 2^i
$$
e.g. $1011=1 \times 2^0 + 1 \times 2^1 + 0 \times 2^3 + 1 \times 2^4$ - Two’s complement:
$$
B2T(X)=-x_{w-1} \cdot 2^{w-1} + \sum_{i=0}^{w-2} x_i \cdot 2^i
$$
e.g. $1011 = −1 \times 2^3 + (1 \times 2^0 + 1 \times 2^1 + 0 \times 2^2 )$
Numeric range of integer representations
Unsigned:
$$
UMin=0=000 \ldots 0
$$
$$
UMax=2^{w−1}= 111 \ldots 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) \cdot 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} \cdot 2^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$