Our goal is to build a four-bit adder. Its inputs are two four-bit numbers, so anything from 0 to 15 in base 10. Its output is another four-bit number. We'll approach it in three steps, following a classical progression used to teach digital electronics since the days when a computer took up a whole room. First we build a "half adder" that can't do much on its own, then a "full adder" that does a single column of addition, then finally the four-bit adder.

In primary school, we learn to do multi-digit addition by writing the numbers in columns:

  33
+ 49
----
  82

When a column adds up to 10 or more, we carry the one into the next column:

  1  <- carried 1 because 3 + 9 >= 10 in the right column
  33
+ 49
----
  82

Computers do addition in a essentially the same way, adding up columns one at a time. The numbers are in binary, though, so each column is a zero or a one. Here's the binary version of 33 + 49 == 82, the same example as above:

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

In base 10, base 2, or any other base, adding two digits gives us both a sum and a carried value. For each column, we need to produce a sum digit plus a carry. We also need to consider the previous column's carry, adding it into the current column's sum.

Putting that together, each column has three inputs: the two digits being added, plus the previous column's carry; and it has two outputs: the sum digit plus a new carry. These three-input-two-output columns are full adders: they can do everything required for one column of binary addition. To get there, we first build a simpler device called a half adder that only does half of the work.