Adding with Gates

Adding two bits

Start with the smallest sum: one bit plus one bit. There are four cases ¹:

1 + 1 is 2, 10 in binary: sum bit 0, carry 1, the same as 5 + 5 in decimal leaving 0 and carrying 1. Read the columns as truth tables: sum is A XOR B, and carry is A AND B ¹. Two gates, and that’s a half adder.

A full adder

A half adder handles the rightmost column. Every other column also has to add the carry coming in from the column to its right, so it needs three inputs: A, B, and carry in ¹. That’s a full adder:

sum       = A XOR B XOR carry_in
carry_out = (A AND B) OR (carry_in AND (A XOR B))

The carry out is 1 when A and B are both 1, or when exactly one of them is 1 and there’s a carry coming in: exactly the cases where the column adds up to 2 or 3.

Four bits and more

To add 4-bit numbers, put four full adders side by side, one per column, and wire each one’s carry out to the next one’s carry in; the rightmost gets a carry in of 0 ¹. Adding 6 (0110) and 7 (0111) column by column, right to left:

• bit 0: 0 + 1 = 1, carry 0
• bit 1: 1 + 1 = 0, carry 1
• bit 2: 1 + 1 + 1 = 1, carry 1
• bit 3: 0 + 0 + 1 = 1, carry 0

Result 1101, 13. Each column can’t finish until the carry from its right arrives, so the carry ripples from the lowest bit to the highest: a ripple-carry adder ¹. Any carry out of the leftmost column doesn’t fit, which is the overflow from module 1, seen from the inside.

Simulating it

You can build all of this in a few lines of code. This program defines one gate, NAND, builds every other gate from it, then a full adder and a 4-bit adder, exactly as above. You don’t need to know Python to follow it; read the definitions as the formulas they are. Save it as gates.py:

# gates.py: logic gates and an adder, built from nothing but NAND.

def nand(a, b):
    return 0 if (a and b) else 1

def not_(a):
    return nand(a, a)

def and_(a, b):
    return not_(nand(a, b))

def or_(a, b):
    return nand(not_(a), not_(b))

def xor(a, b):
    return and_(or_(a, b), nand(a, b))

def full_adder(a, b, carry_in):
    """Add three bits; return (sum bit, carry out)."""
    s = xor(xor(a, b), carry_in)
    carry_out = or_(and_(a, b), and_(carry_in, xor(a, b)))
    return s, carry_out

def add4(a_bits, b_bits):
    """Add two 4-bit numbers given as lists, lowest bit first."""
    carry = 0
    result = []
    for a, b in zip(a_bits, b_bits):
        s, carry = full_adder(a, b, carry)
        result.append(s)
    return result, carry

def to_bits(n):
    return [(n >> i) & 1 for i in range(4)]

def from_bits(bits):
    return sum(bit << i for i, bit in enumerate(bits))

if __name__ == "__main__":
    print("A B | AND OR XOR NAND")
    for a in (0, 1):
        for b in (0, 1):
            print(a, b, "|", and_(a, b), "  ", or_(a, b), " ", xor(a, b), "  ", nand(a, b))
    print()
    for x, y in [(5, 3), (6, 7), (9, 9)]:
        bits, carry = add4(to_bits(x), to_bits(y))
        print(f"{x} + {y} = {from_bits(bits)}, carry out {carry}")

A few notes on reading it: def defines a function; not_, and_, and or_ have a trailing underscore because not, and, and or are Python’s own words; to_bits uses last lesson’s shift and mask, (n >> i) & 1, to pull out bit i. Run it:

me@linuxbox:~$ python3 gates.py
A B | AND OR XOR NAND
0 0 | 0    0   0    1
0 1 | 0    1   1    1
1 0 | 0    1   1    1
1 1 | 1    1   0    0

5 + 3 = 8, carry out 0
6 + 7 = 13, carry out 0
9 + 9 = 2, carry out 1

The truth tables match, built from NAND alone. And 9 + 9: 18 doesn’t fit in four bits (the most is 15), so the adder gives 2 with a carry out of 1, overflow, since 18 = 16 + 2. Checking every one of the 256 possible pairs against Python’s own +, counting the carry as 16, finds no mistakes.

Where adders live

Inside the processor, adders and the other arithmetic and logic circuits make up the arithmetic logic unit, the ALU: the part that executes add, subtract, AND, OR, compare, and so on ¹. Adders also do quieter jobs, like stepping the program counter to the next instruction and working out memory addresses ¹. Subtraction reuses the adder, adding the two’s complement negation (module 1) ¹.

Real processors don’t use plain ripple carry for 64-bit numbers, since waiting for a carry to cross 64 columns is slow; they use circuits that work out carries ahead of time. The idea is the same.

Your turn

So

Adding two bits is XOR for the sum and AND for the carry: a half adder. A full adder adds a carry in as well, and chaining full adders, each carry out feeding the next carry in, gives a ripple-carry adder for numbers of any width; a carry out of the top is overflow. A short program built from a single NAND function reproduces every gate and adds correctly. In the processor, adders form part of the ALU and also step the program counter and calculate addresses.