1.1 Representing Signed Integers
With n bits we can label 2ⁿ patterns. Three schemes compete for representing negatives (examples for 8 bits, value 9):
| Scheme | +9 | −9 | Range (n = 8) | Zeros |
|---|---|---|---|---|
| Sign-magnitude | 00001001 | 10001001 | −127 … +127 | two (+0, −0) |
| 1's complement | 00001001 | 11110110 | −127 … +127 | two |
| 2's complement | 00001001 | 11110111 | −128 … +127 | one |
Why 2's complement won: a single zero, subtraction reduces to addition (A − B = A + B̄ + 1, so one adder circuit does both), and comparison hardware stays simple. The asymmetric range (−128 exists, +128 doesn't) is itself a favourite short question.
To negate: invert every bit, add 1. For 9 = 00001001 → invert 11110110 → +1 → 11110111.
1.2 Worked Subtraction: 23 − 45 in 8 Bits
23 = 0001 0111
45 = 0010 1101
-45 : invert -> 1101 0010, add 1 -> 1101 0011
0001 0111 (23)
+ 1101 0011 (-45)
-----------
1110 1010 (no carry out)Result 11101010 is negative (MSB = 1). Magnitude: invert → 00010101, +1 → 00010110 = 22. So the answer is −22. ✓
1.3 Overflow Detection
Overflow occurs only when adding two same-sign numbers yields the opposite sign. Hardware rule: V = Cin(MSB) ⊕ Cout(MSB) — overflow iff the carry into the sign bit differs from the carry out of it.
Example: 100 + 29 in 8 bits: 01100100 + 00011101 = 10000001 (= −127 as 2's complement). Two positives produced a negative → overflow. Trap: the carry-out flag C and overflow flag V are different things; C matters for unsigned arithmetic, V for signed.
1.4 Half Adder and Full Adder
| x | y | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Half adder: S = x ⊕ y, C = x·y — adds two bits, no carry-in, so it cannot be chained alone.
Full adder adds x, y and carry-in z: S = x ⊕ y ⊕ z, Cout = xy + z(x ⊕ y). It is built from two half adders plus an OR gate — a standard "show how" question.
1.5 Ripple-Carry Adder and Its Delay Problem
Chain n full adders, Cout of stage i feeding Cin of stage i+1. Correct but serial in time: stage 31 cannot finalize until the carry ripples through all earlier stages. With ≈2 gate delays per stage, an n-bit ripple adder needs about 2n gate delays — 64 delays for 32 bits. The adder sits on the CPU's critical path, so this directly limits clock frequency: that is why faster adders exist.
1.6 Carry-Lookahead Adder (CLA)
Define per bit position: Generate Gᵢ = AᵢBᵢ (produces a carry regardless of Cin) and Propagate Pᵢ = Aᵢ ⊕ Bᵢ (passes an incoming carry along). Then every carry is a two-level Boolean function of the inputs:
C1 = G0 + P0.C0
C2 = G1 + P1.G0 + P1.P0.C0
C3 = G2 + P2.G1 + P2.P1.G0 + P2.P1.P0.C0
C4 = G3 + P3.G2 + P3.P2.G1 + P3.P2.P1.G0 + P3.P2.P1.P0.C0All carries emerge after ~3–4 gate delays independent of n (within a block). Cost: the AND/OR terms grow rapidly, so practical designs use 4-bit CLA blocks plus a second-level "group" lookahead over block G/P signals — hierarchy trades a little delay for feasible fan-in.
| Adder | Delay | Hardware | Verdict |
|---|---|---|---|
| Ripple-carry | O(n) ≈ 2n gate delays | n full adders (cheap) | Fine for small n |
| Carry-lookahead | O(1) per block, O(log n) hierarchical | Extra G/P logic (costly) | Standard in real ALUs |
🎯 Exam Focus
- Represent −57 in sign-magnitude, 1's complement and 2's complement using 8 bits.
- Perform (−35) + (−93) in 8-bit 2's complement and state whether overflow occurs, using the Cin ⊕ Cout rule.
- Design a full adder using two half adders and one OR gate; write all Boolean equations.
- Why is a ripple-carry adder slow? Derive the worst-case gate-delay count for 16 bits.
- Define carry generate and propagate. Derive C1–C4 for a 4-bit carry-lookahead adder.
- Why does 8-bit 2's complement represent −128 but not +128? Explain from the encoding.