Computer Arithmetic — Half and Full Adders, Ripple Carry vs Carry Look-Ahead, and Booth's Multiplication

The ALU can only do a few very simple things with logic gates — yet from them it builds addition, subtraction, multiplication and division. This lesson shows how, with the circuits and algorithms that appear in every COA exam.

1. Half adder

Adds two bits A and B:

Sum = A ⊕ B (XOR), Carry = A · B (AND).

2. Full adder

Adds A, B and a carry-in Cin — what you need for every bit position after the first.

Sum = A ⊕ B ⊕ Cin, Cout = A·B + Cin·(A ⊕ B)

Let's check the formulas against plain arithmetic for all 8 input combinations, then chain four full adders into a 4-bit adder:

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

ok = all(full_adder(a, b, c) == ((a + b + c) % 2, (a + b + c) // 2)
         for a in (0, 1) for b in (0, 1) for c in (0, 1))
print("full adder correct for all 8 cases:", ok)

def ripple_add(x, y, bits=4):
    carry, result = 0, 0
    for i in range(bits):                      # LSB first: each carry ripples to the next adder
        s, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
        result |= s << i
    return result, carry

for x, y in [(5, 6), (9, 9), (15, 1)]:
    r, c = ripple_add(x, y)
    print(f"{x:2} + {y:2} = {r:04b} carry {c}  -> {c * 16 + r}")

full adder correct for all 8 cases: True
 5 +  6 = 1011 carry 0  -> 11
 9 +  9 = 0010 carry 1  -> 18
15 +  1 = 0000 carry 1  -> 16

3. Ripple-carry delay vs carry look-ahead

In a ripple-carry adder, bit 1 can't finish until bit 0's carry arrives, bit 2 waits for bit 1, and so on. For n bits the delay grows linearly — O(n). A 64-bit add would be slow.

Carry look-ahead (CLA) computes all carries in parallel using two signals per bit:

• Generate Gᵢ = Aᵢ · Bᵢ (this bit creates a carry by itself)
• Propagate Pᵢ = Aᵢ ⊕ Bᵢ (this bit passes an incoming carry on)

Then C₁ = G₀ + P₀C₀, C₂ = G₁ + P₁G₀ + P₁P₀C₀, … — each carry is a two-level AND-OR expression of the inputs, so delay is nearly constant per block (more gates, much faster). Real CPUs use CLA-style adders in blocks.

4. Subtraction

A − B = A + (2's complement of B) = A + (NOT B) + 1. The same adder does it: invert B's bits with XOR gates and set the first carry-in to 1. That's why 2's complement won.

5. Booth's multiplication algorithm

Multiplying signed numbers by repeated add-and-shift needs special handling for negatives. Booth's algorithm handles 2's complement multiplication directly and skips runs of 1s.

Registers: A (accumulator, starts 0), Q (multiplier), Q₋₁ (extra bit, starts 0), M (multiplicand). Repeat n times (n = number of bits):

…then arithmetic shift right the combined A, Q, Q₋₁ (the sign bit of A is copied). The product is A:Q.

A full simulation that prints every step (4-bit example: 7 × −3):

def booth(m, q, n=4):
    mask = (1 << n) - 1
    M, Q, A, q_1 = m & mask, q & mask, 0, 0
    fmt = lambda v: format(v, f"0{n}b")
    print(f"start      A={fmt(A)} Q={fmt(Q)} Q-1={q_1}   M={fmt(M)}")
    for step in range(1, n + 1):
        pair = (Q & 1, q_1)
        if pair == (1, 0):
            A = (A - M) & mask; op = "A=A-M"
        elif pair == (0, 1):
            A = (A + M) & mask; op = "A=A+M"
        else:
            op = "no op"
        combined = (A << (n + 1)) | (Q << 1) | q_1          # arithmetic shift right of A,Q,Q-1
        sign = A >> (n - 1)
        combined = (combined >> 1) | (sign << (2 * n))
        A, Q, q_1 = (combined >> (n + 1)) & mask, (combined >> 1) & mask, combined & 1
        print(f"step {step}: {op:5}  A={fmt(A)} Q={fmt(Q)} Q-1={q_1}")
    product = (A << n) | Q
    if product >> (2 * n - 1):
        product -= 1 << (2 * n)
    return product

print("result:", booth(7, -3), "| check:", 7 * -3)

start      A=0000 Q=1101 Q-1=0   M=0111
step 1: A=A-M  A=1100 Q=1110 Q-1=1
step 2: A=A+M  A=0001 Q=1111 Q-1=0
step 3: A=A-M  A=1101 Q=0111 Q-1=1
step 4: no op  A=1110 Q=1011 Q-1=1
result: -21 | check: -21

Now test every pair of 4-bit signed numbers (−8 … 7), and see what happens with the most negative multiplicand. Then fix it the way textbooks do — give A and M one extra bit:

def booth_w(m, q, n=4, extra=0):
    w = n + extra                                  # width of A and M
    ma, mq = (1 << w) - 1, (1 << n) - 1
    M, Q, A, q_1 = m & ma, q & mq, 0, 0
    for _ in range(n):
        if (Q & 1, q_1) == (1, 0):
            A = (A - M) & ma
        elif (Q & 1, q_1) == (0, 1):
            A = (A + M) & ma
        c = (A << (n + 1)) | (Q << 1) | q_1
        c = (c >> 1) | ((A >> (w - 1)) << (w + n))  # arithmetic shift: copy A's sign bit
        A, Q, q_1 = (c >> (n + 1)) & ma, (c >> 1) & mq, c & 1
    p, bits = (A << n) | Q, w + n
    return p - (1 << bits) if p >> (bits - 1) else p

pairs = [(m, q) for m in range(-8, 8) for q in range(-8, 8)]
wrong = [(m, q) for m, q in pairs if booth_w(m, q) != m * q]
print("n-bit A:  ", len(pairs) - len(wrong), "of", len(pairs), "correct")
print("all failures have M =", sorted({m for m, q in wrong}))
print("(n+1)-bit A:", all(booth_w(m, q, extra=1) == m * q for m, q in pairs), "for all", len(pairs), "pairs")

n-bit A:   241 of 256 correct
all failures have M = [-8]
(n+1)-bit A: True for all 256 pairs

Every failure has M = −8: its negative (+8) doesn't fit in 4-bit 2's complement, so A − M overflows. With one extra bit in A and M, all 256 products are correct — that's why many textbooks (and GATE questions) note that Booth's algorithm needs an extra bit for the most negative multiplicand.

Why Booth helps: a multiplier like 0111 1110 has long runs of 1s; Booth replaces each run with just one subtraction and one addition, instead of one addition per 1-bit.

6. Division (briefly)

Restoring division repeats: shift A,Q left; A ← A − M; if A became negative, restore A (add M back) and set Q₀ = 0, else Q₀ = 1. After n steps, Q = quotient and A = remainder. Non-restoring division skips the restore step by adding M in the next cycle instead — fewer operations.

Common mistakes

• Using a logical (not arithmetic) shift in Booth's algorithm — the sign bit of A must be copied.
• Mixing up the cases: 10 → subtract, 01 → add.
• Forgetting the initial Q₋₁ = 0.
• Saying CLA uses fewer gates (it uses more gates but less delay).
• Forgetting the most-negative-multiplicand case: −M doesn't fit in n bits; use an extra bit.

Quick recap

• Half adder: S = A⊕B, C = AB. Full adder: S = A⊕B⊕Cin, Cout = AB + Cin(A⊕B).
• Ripple carry delay ∝ n; carry look-ahead uses G = AB, P = A⊕B to compute carries in parallel.
• Subtraction = add the 2's complement (invert + carry-in 1).
• Booth: Q₀Q₋₁ = 10 → A−M, 01 → A+M, then arithmetic shift right; n steps; product in A:Q.