First, a note about representation: we'll represent multi-bit numbers with arrays of 0s and 1s. We could use Python's native integers, but keeping the bits explicit makes it clear that there's no magic involved.

To add multi-bit numbers, we need one full adder per bit. In our case, that's four full adders. The full adders will cascade into each other: the carry output of each full adder feeds the carry input of the next. This is still the same process from primary school: add each column of digits, possibly carrying a 1 over to the next column.

  1    1  <- carried ones
  0100001
+ 0110001
---------
  1010010

Our adder begins with the rightmost, least significant digit in the numbers. For example, the number 1 (in base 10) is 0001 (in base 2), which we represent as [0, 0, 0, 1]. The number 9 (in base 10) is 1001 (in base 2), which we represent as [1, 0, 0, 1].

>>> def ADD4(left, right):
...     carry3, sum3 = FULL(left[3], right[3], 0)
...     carry2, sum2 = FULL(left[2], right[2], carry3)
...     carry1, sum1 = FULL(left[1], right[1], carry2)
...     carry0, sum0 = FULL(left[0], right[0], carry1)
...     return [sum0, sum1, sum2, sum3]

# Check: 0 + 0 == 0
>>> print(ADD4([0, 0, 0, 0], [0, 0, 0, 0]))
[0, 0, 0, 0]

# Check: 1 + 1 == 2
>>> print(ADD4([0, 0, 0, 1], [0, 0, 0, 1]))
[0, 0, 1, 0]

# Check: 7 + 1 == 8
>>> print(ADD4([0, 1, 1, 1], [0, 0, 0, 1]))
[1, 0, 0, 0]

# Check: 7 + 8 == 15 (the largest 4-bit number)
>>> print(ADD4([0, 1, 1, 1], [1, 0, 0, 0]))
[1, 1, 1, 1]

The problem with fixed-size adders like this one (and the ones in all of our computers) is that they stop being "adders" in the everyday sense when numbers get too large. For example, if we try to add 15 + 1, which should give us 16, we get 0 instead.

>>> print(ADD4([1, 1, 1, 1], [0, 0, 0, 1]))
[0, 0, 0, 0]

The adder worked correctly here: it set the final carry variable to 1, but that value was discarded because our function didn't do anything with it. If we built a five-bit adder, that final carry would be an input to the fifth full adder, and we'd get [1, 0, 0, 0, 0], which is 16 in base 10.

As usual, here's the four-bit adder as a circuit diagram made out of our full adder components. The first carry_in and last carry_out are intentionally unused.

Our 4-bit adder is a specific type called a ripple adder because the carry bit "ripples" through the four full adder stages, one by one. This is roughly how integers worked in many early microprocessors. Later, in more advanced processors like Intel's 8008 CPU, faster carry-lookahead designs took over. Modern CPUs contain several adders doing different jobs, each specialized for its task, all of which are more complex than this basic design. Still, ripple adders are both the historical and conceptual basis for modern adders.

The diagram below shows the full four-bit adder with all of the individual AND, OR, and XOR gates shown. We could simplify it in several ways, but some redundancy is left in to show the repetitive structures that we've built up incrementally by reusing gates, half adders, and full adders.

It's not important to read and understand this diagram in detail by tracing each connection. Instead, compare it to the more familiar process of programming. We write high level code broken into self-contained functions and modules, like the the full adders in the diagram above act as "black boxes" with inputs and outputs. Ultimately, our high-level code gets compiled down into native code that would be difficult to read, just as the full diagram below is more difficult than the one above.

Instead of tracing each connection, here are a few salient points to note. Half adders are always one XOR and one AND, with the XOR placed above the AND. (The first half adder is highlighted with a box.) Full adders are always two half adders plus an OR, so a total of two XORs, two ANDs, and one OR. (The second full adder is highlighted with a box.) The four-bit adder is made of four full adders stacked vertically here due to screen width limitations, but they'd be a bit easier to read if they were arranged horizontally.

All of this was built from our original NAND implementation. (Remember: we wrote all of the other gates in terms of NAND!)

We could break the above discrete four-bit adder diagram down even further, showing how each gate can be made from NAND gates. But, like in programming, the final stages of optimization are subtle, repetitive, and better left to automated tools. Our compilers automatically optimize our code when compiling it. Digital electrical engineers' tools automatically optimize their designs as well.

For reference, here are all of the functions from this article in one place, showing the full four-bit adder built from NAND gates. This code has no external dependencies and uses Python as little more than a calculator.

>>> def NAND(x, y):
...     if x == 0 and y == 0: return 1
...     if x == 0 and y == 1: return 1
...     if x == 1 and y == 0: return 1
...     if x == 1 and y == 1: return 0

>>> def NOT(x):
...     return NAND(x, x)

>>> def AND(x, y):
...     return NOT(NAND(x, y))

>>> def OR(x, y):
...     return NAND(NAND(x, x), NAND(y, y))

>>> def XOR(x, y):
...     return AND(OR(x, y),
...                NOT(AND(x, y)))

>>> def HALF(x, y):
...     carry = AND(x, y)
...     sum = XOR(x, y)
...     return (carry, sum)

>>> def FULL(x, y, carry_in):
...     carry1, sum1 = HALF(x, y)
...     carry2, sum2 = HALF(carry_in, sum1)
...     carry_out = OR(carry1, carry2)
...     return (carry_out, sum2)

>>> def ADD4(left, right):
...     carry3, sum3 = FULL(left[3], right[3], 0)
...     carry2, sum2 = FULL(left[2], right[2], carry3)
...     carry1, sum1 = FULL(left[1], right[1], carry2)
...     carry0, sum0 = FULL(left[0], right[0], carry1)
...     return [sum0, sum1, sum2, sum3]

>>> print(ADD4([0, 0, 0, 1], [1, 0, 0, 1]))
[1, 0, 1, 0]