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

Source: https://skills101.in/learn/coa/computer-arithmetic-booth-algorithm — Skills101 free tutorial (Computer Organisation & Architecture (COA)). Updated 2026-11-09.

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`:

| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |

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

![Full adder: inputs A, B and carry-in go through two XOR gates to make the sum; the carry-out comes from A AND B, OR'd with carry-in AND (A XOR B); chaining full adders makes a ripple-carry adder](https://skills101.in/learn-img/coa/full-adder.svg)

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

```python
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}")
```

```text
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):

| Q₀ Q₋₁ | Action |
|---|---|
| 0 0 or 1 1 | nothing |
| 1 0 | A ← A − M |
| 0 1 | A ← A + M |

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

![Booth's algorithm flow: look at Q0 and Q-1; if 10 subtract M from A, if 01 add M to A, otherwise do nothing; then arithmetic shift right A, Q and Q-1 together; repeat n times; the answer is A followed by Q](https://skills101.in/learn-img/coa/booth-flow.svg)

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

```python
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)
```

```text
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**:

```python
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")
```

```text
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.


Practice quiz and free certificate: https://skills101.in/learn/coa/computer-arithmetic-booth-algorithm