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