From Logic Gates to Adders
Computers don't "do arithmetic" — they only build blocks layer by layer with logic gates. In this lecture, we'll build a circuit that can add numbers by hand using XOR, AND, and OR gates, from half adder to full adder to 4-bit adder, constructing step by step.
Addition in Daily Life—Inspired by Column Addition
Recall the process of doing addition on paper. Compute37 + 58：
First calculate the ones digit:7 + 8 = 15, write5，increment by 1。
Then calculate the tens digit:3 + 5 + carry 1 = 9, write9, the result is95。
This process reveals three key points:
1. Bit-by-bit calculation: Each bit only cares about its two addends and the carry from the lower bit.
2. Carry propagation: After the lower bit is computed, a carry may be generated, and this carry must be passed to the higher bit.
3. Least significant bit special: The lowest bit has no carry from a lower bit; it only needs to process the two addends.
Computers do addition with the same idea: break a big problem (multi-bit addition) into many small problems (1-bit addition), then solve them one by one.
Half adder — 1-bit addition for the lowest bit
The lowest bit has no carry input; it only needs to add two 1-bit binary numbers. A circuit that can handle this situation is called aHalf Adder。
A half adder has two inputs A and B, and two outputs:Sum bitandCarry。
Half adder truth table:
| A | B | Sum (sum) | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Looking at the truth table, a surprising coincidence appears:
Sum = A XOR B. When A and B are different, Sum=1; when same, Sum=0 — this is exactly the truth table of an XOR gate.
Carry = A AND B. A carry is generated only when both inputs are 1 — this is exactly the truth table of an AND gate.
Half adder only requires1 XOR gate + 1 AND gateThat can be implemented. George Boole probably never imagined that the algebraic system he invented would one day become the mathematical foundation of adders.
Full Adder—Complete Addition with Carry Handling
The half adder has a fatal flaw:It cannot receive a carry from the lower bit.. Except for the lowest bit, each bit must process three numbers: A, B, and the carry-in Cin from the lower bit.
A circuit that can handle two addends and one carry input at the same time is called aFull Adder。
Full adder truth table:
| 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 |
A clever design:You can build a full adder with two half adders。
Step 1: Half adder 1 processes A and B, producing intermediate sum S1 and carry C1.
Step 2: Half adder 2 processes S1 and Cin, producing final sum Sum and carry C2.
Step 3: Final CarryCout = C1 OR C2(If either half adder generates a carry, the final output is a carry.)
The circuit structure of a full adder:2 half adders + 1 OR gate. Layered on top of each other, each half adder internally is XOR + AND. This hierarchical construction idea runs through the entire computer architecture.
Cascading full adders — 4-bit ripple carry adder
With full adders, multi-bit addition becomes simple:Connect multiple full adders in series, with the carry output of the lower bit connected to the carry input of the higher bit。
The cascade structure of a 4-bit adder:
Bit 0 (lowest bit): full adder processes A0, B0, carry-in = 0, producing sum S0 and carry C0.
Bit 1: full adder processes A1, B1, carry-in = C0, producing sum S1 and carry C1.
Bit 2: full adder processes A2, B2, carry-in = C1, producing sum S2 and carry C2.
Bit 3 (highest bit): full adder processes A3, B3, carry-in = C2, producing sum S3 and carry C3 (final carry).
The carry ripples like water waves from the low bit to the high bit level by level, so this structure is called aRipple Carry Adder (Ripple Carry Adder)。
The ripple carry adder is simple and intuitive, but has a performance bottleneck: in the worst case, the carry must propagate from bit 0 all the way to the highest bit, passing through N stages of full adder delays. Modern CPUs use techniques like carry lookahead to optimize, but understanding ripple carry is a prerequisite for understanding all adder optimizations.
Python Code Demo
Example
# Lecture 8: From Logic Gates to Adders - Python Demo
# example tutorial series
# ============================================
def half_adder(a, b):
"""
Half adder: adds two 1-bit binary numbers, ignoring carry input.
Parameters:
a, b: each is 0 or 1
Returns:
(sum_bit, carry_out): sum bit and carry out
Circuit implementation:
sum_bit = a XOR b (XOR gate)
carry_out = a AND b (AND gate)
"""
sum_bit = a ^ b # XOR: same is 0, different is 1
carry_out = a & b # AND: carry only when both are 1
return sum_bit, carry_out
def full_adder(a, b, carry_in):
"""
Full adder: add two 1-bit binary numbers, considering carry input.
Parameters:
a, b, carry_in: each is 0 or 1
Returns:
(sum_bit, carry_out): sum bit and carry out
Implementation tip—cascade two half adders:
Step 1: half_adder(a, b) → (s1, c1)
Step 2: half_adder(s1, carry_in) → (sum_bit, c2)
Final carry: carry_out = c1 OR c2
"""
s1, c1 = half_adder(a, b)
sum_bit, c2 = half_adder(s1, carry_in)
carry_out = c1 | c2 # OR gate: if either one has a carry, the final carry is set
return sum_bit, carry_out
def adder_4bit(a_bits, b_bits):
"""
4-bit ripple-carry adder: 4 full adders cascaded.
Parameters:
a_bits: 4-bit binary list, a_bits[0] is the least significant bit (LSB)
b_bits: 4-bit binary list, b_bits[0] is the least significant bit (LSB)
Returns:
(sum_bits, final_carry): 4-bit sum (least significant bit first) and final carry
Print the complete process of carry propagation, demonstrating how ripple carry works.
"""
carry_in = 0
sum_bits = []
print("=" * 55)
print(4-bit ripple carry adder — carry propagation process)
print("=" * 55)
# Display high-order bits first, for easy reading
print(f" Addend A: {list(reversed(a_bits))} (high bits first)")
print(f" Addend B: {list(reversed(b_bits))} (high bits first)")
print()
for i in range(4):
s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
sum_bits.append(s)
print(f" [bit {i}] (the least significant bit is bit 0)")
print(f" Input: A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, enterbits入={carry_in}")
print(fOutput: sum bit={s}, carry out={carry_out})
if carry_out:
print(f>> Carry generated! Carry={carry_out} will be passed to bit {i+1})
carry_in = carry_out # The current carry becomes the carry input of the next bit
print()
print(fCalculation result: {list(reversed(sum_bits))} (high-order bits first))
print(fFinal carry: {carry_in})
print("=" * 55)
return sum_bits, carry_in
def decimal_to_4bit(n):
"""Convert decimal numbers 0-15 to 4-bit binary lists (least significant bit first)"""
return [(n >> i) & 1 for i in range(4)]
def bits_to_decimal(bits):
"""Convert a list of binary bits (least significant bit first) to a decimal integer"""
return sum(bit * (2 ** i) for i, bit in enumerate(bits))
# ============================================
# Test case
# ============================================
print(>>> example half adder test <<<)
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f" half_adder({a}, {b}) => sum={s}, carry={c}")
print()
print(>>> example full adder test <<<)
test_cases = [
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
s, c = full_adder(a, b, cin)
print(f" full_adder({a}, {b}, carry_in={cin}) => sum={s}, carry={c}")
print()
print(>>> example 4-bit adder test: 7 + 5 <<<)
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(fExpected: {a_dec} + {b_dec} = {a_dec + b_dec})
print(fResult: {result_dec} (carry={final_carry}))
print(f" example verify: {'Through!' if result_dec == a_dec + b_dec else 'failure!'}")
print()
print(>>> example extra test: 10 + 6 (possible overflow) <<<)
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" Expected: 10 + 6 = 16")
print(f" 4 bitsResult: {result_dec2}, enterbits: {carry2}, Complete 5 bitsValue: {full_result}")
print(fexample verification: {'Pass!' if full_result == 16 else 'Fail!'})
Run the code and observe how the carry propagates between each bit—the least significant bit is computed first, and after a carry is generated, it is passed to the next bit; the next bit is then computed, and if a carry is generated, it is passed further along. This is the origin of the name "ripple carry."
Interactive demo: 4-bit adder cascade animation (example carry propagation demo)
Below, a 4-bit ripple carry adder is simulated with pure div+SVG.Click the button to step through how the carry propagates from bit 0 (least significant bit) to bit 3 (most significant bit)., or you can use "Auto Demo" to watch the full process.