How an Adder Is Built
How an Adder Is Built
When you were a kid, you might have played with building blocks. A single block by itself is nothing special. But snap them together and you can build a bridge, a castle, a complex machine. Digital circuits work exactly the same way. In the last two chapters we met AND, OR, and NOT gates — our fundamental building blocks. Now let's see what happens when we snap them together to make a circuit that can actually do arithmetic.
By the end of this chapter, you should feel a satisfying "aha!" — the same feeling engineers had when they first realized that mathematics and electricity are speaking the same language.
Core Principles
Step 1: The Half Adder
Start with the simplest possible case: adding two single-bit binary numbers. There are only four possibilities:
0 + 0 = 00 (sum 0, carry 0)
0 + 1 = 01 (sum 1, carry 0)
1 + 0 = 01 (sum 1, carry 0)
1 + 1 = 10 (sum 0, carry 1) ← just like decimal 1+1=2; "2" in binary is "10"
We need two outputs: the Sum digit and the Carry digit.
Look for patterns:
- Sum = A XOR B (different inputs → 1; same inputs → 0)
- Carry = A AND B (only 1+1 produces a carry)
Wire those two gates up and you have a half adder:
A ─┬──[XOR]──── Sum
B ─┤
└──[AND]──── Carry
Truth table verification:
| A | B | Sum (A XOR B) | Carry (A AND B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
It works. But it's called a half adder for a reason: it can only handle the least significant bit. For any other position in a multi-bit number, you also need to account for a carry coming in from the previous bit. That's where the full adder comes in.
Step 2: The Full Adder
A full adder takes three inputs: A, B, and Cin (carry-in from the lower bit). It produces two outputs: Sum and Cout (carry-out to the next higher bit).
Inputs: A, B, Cin
Outputs: Sum, Cout
Eight possible input combinations:
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
The patterns:
- Sum = A XOR B XOR Cin
- Cout = (A AND B) OR (Cin AND (A XOR B))
The beautiful thing: you can build a full adder from two half adders and one OR gate.
┌─────────────┐ ┌─────────────┐
A ──────→│ │ │ │
│ Half Adder │─Sum1──→│ Half Adder │─────── Sum
B ──────→│ 1 │ │ 2 │
└─────────────┘ ┌──→│ │
│ │ └─────────────┘
│ Carry1 │ │ Carry2
│ │ │
Cin ──────────┘ │ ┌────┘
└───┤ OR ├──── Cout
└────┘
Step 3: The 4-Bit Ripple-Carry Adder
Chain four full adders together — each one's Cout feeds into the next one's Cin — and you have a 4-bit adder:
A3B3 A2B2 A1B1 A0B0
│ │ │ │
↓ ↓ ↓ ↓
0→[FA3]←[FA2]←[FA1]←[FA0]
│ │ │ │
S3 S2 S1 S0
Carry flows right-to-left (low bit to high bit),
rippling like a wave — hence "ripple-carry adder"
Let's trace through 6 + 5 = 11 (binary 0110 + 0101):
FA0: A=0, B=1, Cin=0 → S0=1, Cout=0
FA1: A=1, B=0, Cin=0 → S1=1, Cout=0
FA2: A=1, B=1, Cin=0 → S2=0, Cout=1
FA3: A=0, B=0, Cin=1 → S3=1, Cout=0
Result: 1011 = 11 ✓
Scale this up to 8, 16, or 64 bits by chaining more full adders. That's it — that's the core of every arithmetic operation your computer performs.
Hands-On Verification
Simulate the entire thing from the gate level in Python:
# Basic gates
def XOR(a, b): return a ^ b
def AND(a, b): return a & b
def OR(a, b): return a | b
# Half adder
def half_adder(a, b):
return XOR(a, b), AND(a, b) # (sum, carry)
# Full adder: two half adders + one OR
def full_adder(a, b, cin):
s1, c1 = half_adder(a, b)
s2, c2 = half_adder(s1, cin)
cout = OR(c1, c2)
return s2, cout # (sum, carry_out)
# 4-bit ripple-carry adder
def ripple_carry_4bit(a_bits, b_bits):
"""
a_bits, b_bits: lists of 4 bits, [MSB, ..., LSB]
"""
carry = 0
result = [0] * 4
for i in range(3, -1, -1): # process from LSB (index 3) to MSB (index 0)
result[i], carry = full_adder(a_bits[i], b_bits[i], carry)
return result, carry # (result bits, overflow carry)
# Test: 6 + 5 = 11
a = [0, 1, 1, 0] # 6 = 0110
b = [0, 1, 0, 1] # 5 = 0101
result, overflow = ripple_carry_4bit(a, b)
a_dec = int(''.join(map(str, a)), 2)
b_dec = int(''.join(map(str, b)), 2)
r_dec = int(''.join(map(str, result)), 2)
print(f"A = {''.join(map(str, a))} = {a_dec}")
print(f"B = {''.join(map(str, b))} = {b_dec}")
print(f"Result = {''.join(map(str, result))} = {r_dec}")
print(f"Overflow carry = {overflow}")
print(f"Full result ({overflow}{''.join(map(str,result))}) = {overflow*16 + r_dec}")
# Also verify all 4-bit combinations
errors = 0
for x in range(16):
for y in range(16):
a_bits = [(x >> i) & 1 for i in range(3, -1, -1)]
b_bits = [(y >> i) & 1 for i in range(3, -1, -1)]
r_bits, ov = ripple_carry_4bit(a_bits, b_bits)
r = ov * 16 + int(''.join(map(str, r_bits)), 2)
if r != x + y:
print(f"ERROR: {x} + {y} = {r}, expected {x+y}")
errors += 1
print(f"\nAll 256 test cases passed: {errors == 0}")
Output:
A = 0110 = 6
B = 0101 = 5
Result = 1011 = 11
Overflow carry = 0
Full result (01011) = 11
All 256 test cases passed: True
Every single-digit addition your computer does flows through a circuit structurally identical to what you just simulated.
🔬 Going Deeper
The Ripple-Carry Bottleneck
Ripple-carry adders have a speed problem: carry must propagate sequentially from the least significant bit to the most significant bit. Each full adder adds a small gate delay, and for a 64-bit adder those delays stack up. In a high-frequency CPU, waiting 64 gate delays per addition is unacceptable.
The solution is the Carry-Lookahead Adder (CLA). Instead of waiting for carry to ripple, it predicts carry for every bit simultaneously using two derived signals:
- G (Generate): G = A AND B — this bit will produce a carry regardless of Cin
- P (Propagate): P = A XOR B — this bit will pass along a carry if it receives one
With G and P computed for every bit position in parallel, the carry into any bit position can be calculated directly from the original A and B inputs — no waiting. A 64-bit carry-lookahead adder reduces carry delay from ~64 gate levels to ~4–5, a speedup of over 10×. All modern CPUs use CLA-based arithmetic.
Subtraction, Multiplication, Division
Chapter 2 showed that two's complement turns subtraction into addition. Multiplication is repeated addition (specifically, shift-and-add, mirroring long multiplication by hand). Division is repeated subtraction. Modern CPUs include dedicated multiplier and divider circuits optimized for speed, but if you trace the logic deep enough, everything reduces to full adders at the bottom of the stack. The adder is truly the atom of arithmetic hardware.
Recommended Reading
- Computer Organization and Design (Patterson & Hennessy) — Chapter 3 covers hardware arithmetic implementation in full depth, from adders through floating-point units. This is the definitive university textbook on computer architecture. Reading it alongside this chapter is like switching from a tourist map to a detailed survey.
- Hacker's Delight (Henry S. Warren Jr.) — A delightful book entirely devoted to integer arithmetic tricks and bit manipulation. Every chapter is essentially a tour of what adder circuits inspire clever programmers to do. An unexpected joy for anyone curious about the boundary between hardware and software.