COD Chapter 3 — Arithmetic for Computers

Two’s complement, overflow detection, the multiply & divide algorithms, and IEEE 754 floating point.

Sections

Quick summary

2'S COMPLEMENT (n bits): MSB weight is NEGATIVE.
  4-bit 1111 = -8+4+2+1 = -1 · 0101 = 4+1 = 5
  Negate: flip all bits, add 1.     Range: -2^(n-1) … 2^(n-1)-1
  SIGN EXTEND: copy the MSB leftwards (1001 → 1111 1001).
  A - B = A + (1's comp of B) + 1.  Ignore the final carry-out.

OVERFLOW (slide 19) — result has the WRONG SIGN:
  A+B:  (+)+(+) → (-)   ·   (-)+(-) → (+)
  A-B:  (+)-(-) → (-)   ·   (-)-(+) → (+)
  Same-sign add, or opposite-sign subtract, are the only risky cases.

MULTIPLY (slides 26-27): Product = 0; repeat n times:
  1. if Multiplier0 = 1 → Product += Multiplicand
  2. shift Multiplicand LEFT 1     3. shift Multiplier RIGHT 1
  n-bit × m-bit ⇒ (n+m)-bit product.   Time O(m) · Space O(n+m)
  Hardware: 2n-bit Multiplicand reg · 2n-bit ALU · n-bit Multiplier · 2n-bit Product.

DIVIDE: Rem = Dividend; n+1 steps of  Rem -= Divisor ;
  Rem < 0 → restore (+Divisor), shift Q left with 0
  Rem ≥ 0 → shift Q left with 1 ;  then shift Divisor RIGHT.
  MIPS: Lo = quotient, Hi = remainder.

IEEE 754 SINGLE (32-bit): 1 sign · 8 exponent · 23 significand.  bias = 127
  DOUBLE (64-bit): 1 · 11 · 52.  bias = 1023
  value = (-1)^s x (1 + significand) x 2^(exponent - bias)
  STORED exponent = real exponent + bias.  Leading 1. is HIDDEN.
  Steps: decimal → binary → normalize 1.yy x 2^zz → pack.
  exp all-0 & frac 0 ⇒ 0 · exp 255 & frac 0 ⇒ ±∞ · exp 255 & frac≠0 ⇒ NaN