Adders: from half adder to ripple carry

Addition is the heart of every processor's arithmetic unit, and it is built from the gates you already know.

Half adder

Adding two bits gives a 2-bit answer: 0 + 0 = 00, 0 + 1 = 01, 1 + 1 = 10. The low bit is the sum, the high bit the carry:

• sum = A ⊕ B
• carry = A · B

Full adder

To add longer numbers, every column after the first also has a carry in from the column to its right. A full adder adds three bits:

• S = A ⊕ B ⊕ Cin
• Cout = AB + Cin(A ⊕ B): a carry when both bits are 1, or when one is and a carry came in.

Ripple-carry adder

Chain n full adders: each one's carry out is the next one's carry in. Step through 7 + 5 in four bits, and watch the carry travel left:

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

a = [0, 1, 1, 1]       # 7, most significant bit first
b = [0, 1, 0, 1]       # 5
carry, total = 0, [0, 0, 0, 0]
for i in range(3, -1, -1):          # from the rightmost bit
    total[i], carry = full_adder(a[i], b[i], carry)
    print("bit", 3 - i, ": sum", total[i], "carry", carry)
print("result:", total, "carry out:", carry)

The weakness is speed: the last bit must wait for the carry to ripple through every adder before it, so the delay grows with the number of bits. Real processors use carry-lookahead adders, which work out all the carries at once from "generate" (AB) and "propagate" (A ⊕ B) signals.

Subtraction

In two's complement, −B = B' + 1 (flip the bits, add 1). So A − B = A + B' + 1: put an XOR gate on each B input to flip it, and set the first carry in to 1. One circuit adds and subtracts.

def add(a, b, carry):
    out = [0] * len(a)
    for i in range(len(a) - 1, -1, -1):
        out[i] = a[i] ^ b[i] ^ carry
        carry = (a[i] & b[i]) | (carry & (a[i] ^ b[i]))
    return out

a = [0, 1, 0, 1]                   # 5
b = [0, 0, 1, 1]                   # 3
flipped = [1 - bit for bit in b]   # B'
print("5 - 3 =", add(a, flipped, 1))    # A + B' + 1

Overflow

With n bits, two's complement holds −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1 (−8 to 7 for 4 bits). If two numbers of the same sign give a result of the other sign, the answer did not fit: overflow. 7 + 5 = 12 does not fit in 4 bits, and the adder gives 1100 = −4. (A carry out of the top bit is a different thing: it signals that an unsigned result did not fit.)

Mark lesson complete