Chapter 3 – The CPU (Slides 5 – 23): In-Depth Notes with Examples

Introduction: Number Systems & Why Binary Matters

√* A **number system** is a way to write quantities using a fixed set of symbols and a
positional base (radix).

√* Everyday arithmetic uses **decimal (base-10)** with symbols 0-9. Each position is a
power of 10.

√* Computers prefer **binary (base-2)** because electronic circuits have two stable states
(low/high voltage).

√* Other bases you may see: **octal (base-8)** and **hexadecimal (base-16)**—shortcuts
to group binary digits.

√* Positional value rule: In any base B, the right-most digit is worth B⁰, the next B¹, then B²,
etc.

Examples:

√* 19₁₀ → binary: 19 ÷2 remainders → 10011₂.

√* 19₁₀ → octal: group binary in 3s → 23₈.

√* 19₁₀ → hexadecimal: group binary in 4s → 13₁₆.

√* Binary 101101₂ → decimal: (1×32)+(0×16)+(1×8)+(1×4)+(0×2)+(1×1)=45₁₀.

√* Why hex? A single hex digit represents exactly four binary bits (e.g., A₁₆ = 1010₂),
making long binary easier to read.

Slide 5 – Integer Representation (Basics)

Detailed Explanations:

√* Binary digits (bits) are the alphabet of a computer; every quantity must be encoded with
0s and 1s.

√* Integers are whole numbers (no fractional part). Two storage forms: unsigned (always
positive) and signed (can be positive or negative).

√* A binary **point** (similar to a decimal point) separates whole part from fractional part;
slides example: –1101.0101₂.

√* Prefix “0b” or subscript “₂” is often used to show a value is binary; “₁₀” marks decimal.

√* Length in bits matters: with 8 bits you can encode 256 distinct patterns (0–255
unsigned).
Examples:

√* Unsigned 8-bit 00101001₂ = 41₁₀.

√* Signed vs unsigned: 11111111₂ is 255₁₀ unsigned, but could be –1₁₀ in two’s

complement (signed).

√* Fractional binary: 0.101₂ = ½ + 0 + ⅛ = 0.625₁₀.

√* Show negative in human form: –13.3125 given as –1101.0101₂; fractional bits are ½, ¼,
⅛, 1⁄16.

√* Bit-length expansion doubles range: 16 bits unsigned covers 0–65 535₁₀.

Slide 6 – Unsigned Binary Numbers

Detailed Explanations:

√* “Unsigned” means there is **no sign bit**; all patterns map to non-negative values only.

√* Place-value method: bit i (counting from 0 on the right) is worth 2ⁱ if it contains 1.

√* Total value is the sum of all active place-values; bits with 0 contribute nothing.

√* Unsigned arithmetic wraps when the sum exceeds the maximum pattern (modulo 2ⁿ).

√* Unsigned representation is natural for addresses, counters, sizes where negatives make
no sense.

Examples:

√* Binary 10000000₂ (8 bits) = 128₁₀.

√* 00001111₂ = 15₁₀.

√* 10101010₂ = 170₁₀.

√* Show addition: 0101₂ (5) + 0110₂ (6) = 1011₂ (11).

√* Wrap-around: 11111111₂ (255) + 1 → 00000000₂ (0) when stored as 8 bits.

Slide 7 – Signed-Magnitude Representation

Detailed Explanations:

√* The most significant bit (MSB) acts purely as a sign flag: 0 = positive, 1 = negative.

√* Magnitude bits (remaining n–1) store the absolute value using regular binary.

√* There are two encodings for zero: +0 (00000000₂) and –0 (10000000₂).

√* Arithmetic hardware must examine sign bits separately, making addition/subtraction
slower.

√* Rarely used in CPUs today but still appears in some floating-point standards for the sign
bit.

Examples:

√* 8-bit 00000101₂ → +5₁₀.

√* 8-bit 10000101₂ → –5₁₀.

√* 8-bit 01111111₂ → +127₁₀ (largest positive representable).

√* 8-bit 11111111₂ → –127₁₀ (largest negative magnitude).

√* Adding +3 (00000011₂) and –2 (10000010₂) requires manual sign handling.

Slide 8 – Drawbacks of Signed-Magnitude

Detailed Explanations:

√* Dual zero encodings complicate comparisons (software must test both patterns).

√* Adding opposite-signed numbers needs compare-then-subtract logic instead of simple

adders.

√* Carry-out handling becomes ambiguous because sign isn’t part of magnitude.

√* Hardware must convert results back to signed-magnitude form after operations.

√* These inefficiencies pushed designers to adopt two’s complement universally for

integers.

Examples:

√* +0 (00000000₂) and –0 (10000000₂) compare equal in math but differ bitwise.

√* Try adding +1 (00000001₂) and –1 (10000001₂): requires special routine, not simple
binary adder.

√* Adding +127 (01111111₂) and +1 (00000001₂) overflows magnitude field but sign
remains 0 (wrong).

√* Detecting zero: must check for both 00000000₂ or 10000000₂.

√* Subtraction of two negatives (e.g., –5 – (–3)) needs magnitude comparison first.

Slide 9 – Two’s Complement Representation

Detailed Explanations:
√* MSB still acts as sign but also contributes value of –2ⁿ⁻¹ when set.

√* Positive numbers are identical to unsigned encoding (easy reading).

√* Negative numbers are encoded by formula: value = –(2ⁿ – magnitude).

√* Negation rule: invert all bits then add 1; this works because of modulo 2ⁿ arithmetic.

√* A single zero encoding (all bits 0) simplifies equality checks and arithmetic.

Examples:

√* +18 → 00010010₂.

√* Negate +18: 11101101₂ +1 → 11101110₂ = –18.

√* 8-bit 11111111₂ = –1₁₀.

√* 8-bit 10000001₂ = –127₁₀.

√* Adding –5 (11111011₂) + –3 (11111101₂) → 11111000₂ (–8).

Slide 10 – Two’s Complement Range Limits

Detailed Explanations:

√* For n bits, minimum value = –2ⁿ⁻¹, maximum = 2ⁿ⁻¹ – 1.

√* Range is asymmetric by 1 because zero occupies a positive code slot.

√* Overflow occurs when a result falls outside this closed interval.

√* Bit-width dictates how many distinct integer values hardware can represent.

√* Programmers pick 8/16/32/64-bit widths depending on needed range.

Examples:

√* 8 bits: –128 … +127.

√* 16 bits: –32 768 … +32 767.

√* 32 bits: –2 147 483 648 … +2 147 483 647.

√* Adding +120 and +20 in 8-bit → 140 (10001100₂) > 127 → overflow flag set.

√* Subtracting –128 – 1 can’t be represented in 8-bit (underflow).

Slide 11 – Sign Extension (Changing Bit-Width)

Detailed Explanations:
√* When widening a two’s-complement number, replicate the sign bit into new higher
positions.

√* This keeps numerical value identical across bit-widths.

√* For signed-magnitude, you replicate sign bit once, pad rest with zeros (not used much).

√* Zero extension is used only for unsigned numbers (pad new bits with 0).

√* Sign extension is handled automatically in many instruction sets when moving between
register sizes.

Examples:

√* -18 (8-bit) 11101110₂ → 16-bit 1111111111101110₂.

√* +18 (8-bit) 00010010₂ → 16-bit 0000000000010010₂.

√* -1 (8-bit) 11111111₂ → 32-bit 0xFFFFFFFF.

√* Unsigned 255 (8-bit) becomes 00000000000000000000000011111111₂ in 32-bit

without sign.

√* Hardware usually performs sign-extension on load-byte instructions.

Slide 12 – Negating (Forming Two’s Complement)

Detailed Explanations:

√* Step 1: bitwise NOT (~) – flip 0 ↔ 1.

√* Step 2: add 1 to the inverted pattern.

√* Negating twice returns to original value (except for most negative number).

√* Negation is equivalent to arithmetic operation (0 – X).

√* ALUs use this property to implement subtraction with a single adder.

Examples:

√* +5 → 00000101₂ → invert 11111010₂ → add 1 → 11111011₂ = –5.

√* -7 (11111001₂) inverted 00000110₂ +1 → 00000111₂ = +7.

√* 0 negated: 00000000₂ → 11111111₂ +1 → 00000000₂.

√* -128 (10000000₂) inverted 01111111₂ +1 → 10000000₂ (unchanged).

√* CPU instruction NEG r/m8 performs these two steps in hardware.

Slide 13 – Negating Zero (Special Case)
Detailed Explanations:

√* Zero has only one encoding in two’s complement.

√* Negating 0 produces 0; carry-out bit is discarded.

√* Processor flags: Zero flag remains 1, Carry flag cleared, Overflow cleared.

√* Edge behaviour useful for reset logic: flipping sign of 0 is a no-op.

√* Ensures mathematical consistency: –0 = 0.

Examples:

√* 0 → invert: 11111111₂, +1 → 1 00000000₂ → trim to 8 bits → 00000000₂.

√* Assembly: MOV AL,0; NEG AL → AL still 0.

√* Zero extend 0 from 8 to 16 bits stays 0.

√* Sign extend 0 from 8 to 16 bits stays 0.

√* Comparing 0 and –0 in signed magnitude would differ, but in two’s complement equal.

Slide 14 – Edge Case: Most Negative Value (e.g., -128)

Detailed Explanations:

√* Pattern 10000000₂ (–128) negates to itself in 8-bit two’s complement.

√* Reason: +128 can’t be encoded because max positive is +127.

√* Negating tries to produce +128 but wraps to –128 (overflow).

√* Overflow flag is set when negating the most negative value.

√* Software must guard against this when taking absolute values.

Examples:

√* -128 invert: 01111111₂ +1 → 10000000₂ (no change).

√* ABS(-128) on many CPUs still returns –128 (check overflow flag).

√* 16-bit most negative value: 8000₁₆ (–32 768).

√* 32-bit most negative: 0x80000000 (–2 147 483 648).

√* Adding 1 to 0x7FFF (32 767) gives 0x8000 (–32 768) showing wrap.
Slide 15 – Binary Addition
Detailed Explanations:

√* Addition is performed bit-by-bit with carry propagation from LSB upward.

√* Same logic works for unsigned and two’s complement (modulo 2ⁿ).

√* Full-adder circuit outputs Sum = A ⊕ B ⊕ Carry-in, Carry-out = majority(A,B,Carry-in).

√* Carry-out beyond MSB is ignored in signed arithmetic but may be flagged for unsigned.

√* Addition is associative and commutative over fixed width modulo arithmetic.

Examples:

√* 0101₂ (5) + 0011₂ (3) → 1000₂ (8).

√* 1110₂ (14) + 0001₂ (1) → 1111₂ (15).

√* 7 + (–3): 00000111₂ + 11111101₂ = 000000100₂ → 00000100₂ (4) after truncating

carry.

√* –5 + (–6): 11111011₂ + 11111010₂ = 1 11110101₂ → 11110101₂ (–11).

√* Carry chain in 4-bit adder: 0111₂ + 0001₂ triggers 3 carry propagations.

Slide 16 – Overflow Detection in Addition

Detailed Explanations:

√* Overflow when adding two positives yields a negative or two negatives yield positive.

√* Hardware rule: Overflow flag = Carry-into-MSB XOR Carry-out-of-MSB.

√* Carry flag is not reliable for signed overflow in two’s complement.

√* Signed overflow may require exception handling in safe languages.

√* Unsigned arithmetic treats carry-out as wrap indicator.

Examples:

√* 01111111₂ (127) + 00000001₂ (1) → 10000000₂ (–128) → overflow.

√* 10000000₂ (–128) + 11111111₂ (–1) → 01111111₂ (127) → overflow.

√* Adding 50 + 80 in 8-bit unsigned → 130 (10000010₂) fits, no overflow.

√* Carry flag set without signed overflow: 11111111₂ + 00000001₂ → 00000000₂ (carry).

√* Detect overflow formula example: carries 1 (carry into MSB) vs 0 (carry out) → flag = 1.
Slide 17 – Subtraction via Two’s Complement
Detailed Explanations:

√* Subtraction A – B = A + (two’s complement of B).

√* Thus only one adder is needed for both add & subtract in hardware.

√* Borrow logic is handled automatically through carry chain.

√* Overflow detection uses same rule as addition.

√* CPU instruction “SUB” feeds complemented bits internally.

Examples:

√* 9 – 5: 00001001₂ + (11111011₂) = 00000100₂ (4).

√* 20 – 12: 00010100₂ + (11110100₂) = 00001000₂ (8).

√* -3 – 4: 11111101₂ + 00000100₂ = 000000010₁₀ → 11111001₂ (–7).

√* 5 – 9 => overflow negative: 00000101₂ + 11110111₂ = 1111100₁₂ → 1111100₁₂ (–4).

√* Detect borrow in unsigned: if Carry flag = 0 after subtraction means borrow occurred.

Slide 18 – Worked Subtraction Example (Slide Illustration)

Detailed Explanations:

√* Example 12₁₀ – 20₁₀ using two’s complement on 8 bits.

√* Two’s complement of 20: 00010100₂ invert → 11101011₂ +1 → 11101100₂.

√* Add to 12 (00001100₂) gives 11111000₂.

√* Result 11111000₂ is –8₁₀ after interpretation.

√* Overflow does not occur because operands have different signs.

Examples:

√* Verify: –8 + 20 = 12 (reverse operation).

√* Binary to decimal check: 11111000₂ = –8 (invert+1 gives 00001000₂ = 8).

√* Unsigned view would see 248 — highlights need to know signedness context.

√* Compute 15 – (–2): complement –2 (11111110₂) → 00000010₂;

00001111₂+00000010₂=00010001₂ (17).

√* Compute –5 – (–5): results in 0; flags: Zero=1, Overflow=0.

Slide 19 – Hardware for Addition/Subtraction
Detailed Explanations:

√* ALU uses a single ripple-carry or carry-look-ahead adder core.

√* Subtraction achieved by XORing second operand with 1s and forcing Carry-in=1.

√* Flags (Zero, Sign, Carry, Overflow) latch outputs for CPU status register.

√* Muxes (multiplexers) select operands from registers or immediate data.

√* Control unit issues an “Add/Sub” signal based on opcode.

Examples:

√* 8086 ALU width 16 bits; modern x86-64 uses 64-bit adders.

√* Carry-look-ahead reduces propagation delay from O(n) to O(log n).

√* ARM subtract instruction (SUB) sets flags; RSBS “reverse subtract & set flags”.

√* Adding hardware cost: subtract requires only 1 extra XOR per bit.

√* Overflow flag path wired as (Carry_in_to_MSB XOR Carry_out_of_MSB).

Slide 20 – Binary Multiplication (Shift-and-Add)

Detailed Explanations:

√* Analogous to long-multiplication in decimal but with base 2.

√* Multiplicand is copied when multiplier bit is 1; otherwise copy 0.

√* Each copy is shifted left according to bit position (equiv. multiply by 2ᵏ).

√* Partial products summed to form final result; may double bit-length.

√* Signed multiplication extends sign bits to keep correctness.

Examples:

√* 1011₂ (11) × 1101₂ (13) worked out on slide.

√* 1-bit multiplier: 1011₂ × 1 → 1011₂ (shift 0).

√* 2² bit set: 1011₂ shifted 2 → 101100₂ = 44₁₀.

√* Combining partials of 3 and 4 yields 143₁₀.

√* Unsigned 3 (11₂) × 4 (100₂) → partials: 000, 1100 = 1100₂ (12).

Slide 21 – Partial Products & Result Length
Detailed Explanations:

√* Each multiplier bit potentially yields one partial product of n or (n+1) bits.

√* n-bit × n-bit multiplication needs space for 2n-bit result (to hold largest value).

√* When multiplier bit is 0, partial product is 0 (saves additions in hardware).

√* Booth’s algorithm reduces number of partial products for signed numbers.

√* Carry-save adders can sum three numbers at once, speeding multiplication.

Examples:

√* 8-bit × 8-bit → 16-bit product; 255 × 255 = 65 025 (> 8 bits).

√* 4-bit 1010₂ × 0101₂ has at most four partial products.

√* Partial products for 0101₂: 0000, 1010, 0000, 101000.

√* Hardware saves zeros by skipping add when bit=0.

√* Signed –3 × 2: sign-extend multiplicand to handle negative correctly.

Slide 22 – Hardware Implementation of Multiplication

Detailed Explanations:

√* Simple CPU may reuse adder over many cycles (shift-add algorithm).

√* High-performance CPU includes dedicated multiplier with parallel partial-product

generation.

√* Wallace tree or Dadda tree structures sum partial products quickly.

√* Pipelined multipliers can output a product every clock after initial latency.

√* Hardware cost grows roughly with n² gates for straightforward multipliers.

Examples:

√* MIPS R2000 executes MUL in 10 cycles (shift-add).

√* Intel Core uses 3-cycle latency, 1-cycle throughput 64×64→128-bit multiplier.

√* FPGA DSP blocks implement 18×18-bit signed multipliers.

√* Booth-encoded multiplier halves number of adders vs naïve.

√* ARM “MUL” and “SMULL” instructions produce 32-bit or 64-bit results respectively.
Slide 23 – Reading Assignment & Next Steps
Detailed Explanations:

√* Textbook section pp 302-317 deepens integer multiplication methods including Booth’s,

array, Wallace tree.

√* Section pp 317-328 introduces floating-point format (IEEE 754) and arithmetic rules.

√* Understanding integer arithmetic is prerequisite for grasping floating-point rounding

behaviour.

√* Next class covers CPU instruction set designs (RISC vs CISC).

√* Review quiz: Convert –45 to 8-bit two’s complement before class.

Examples:

√* Reading check: After pp 317-328, list three special IEEE-754 values (NaN, +∞, –∞).

√* Exercise: Multiply 0x0F and 0x73 using binary long-multiplication.

√* Quiz: What is the range of 12-bit two’s complement? (–2048…+2047).

√* Find overflow: 0x7FFF + 0x0002 in 16-bit signed? (overflow).

√* Design task: Sketch truth table for 1-bit full adder (A,B,C_in→Sum,C_out).