Ripple-Carry Adder

Adding like in primary school

When you add 47 + 38 on paper you add the rightmost column, write the digit, carry the extra and move left. A binary adder does exactly this, one full adder per column.

The full adder

A full adder takes three bits, A, B and carry-in, and produces two:

sum       = A XOR B XOR carry-in
carry-out = (A AND B) OR (carry-in AND (A XOR B))

Chaining them

Connect the carry-out of each adder to the carry-in of the next. The first carry-in is 0. The carry ripples upward, which gives the circuit its name.

Example: 11 + 6 = 1011 + 0110

The final carry becomes bit 4, giving 10001 = 17.

Speed

Bit 3 cannot produce its sum until bit 2’s carry is ready, which waits for bit 1, and so on. The delay is O(n). Real CPUs use carry-lookahead adders that work out all carries at once from “generate” (A AND B) and “propagate” (A XOR B) signals, so 64-bit addition still takes only a few gate delays.

Overflow

With unsigned numbers, a carry out of the top bit means the result does not fit. With two’s complement numbers, overflow happens when two numbers of the same sign give a result of the opposite sign.

Code

def ripple_add(a, b, n=4):
    carry, total = 0, 0
    for i in range(n):
        x, y = (a >> i) & 1, (b >> i) & 1
        total |= (x ^ y ^ carry) << i
        carry = (x & y) | (carry & (x ^ y))
    return total | (carry << n)

print(ripple_add(11, 6))   # 17

Common mistakes

• Forgetting the carry-in when filling the truth table: a full adder has three inputs, not two.
• Reading the sum from left to right. Bit 0 is the rightmost bit.
• Dropping the final carry. In an unsigned add it is the fifth bit of the answer.