The adder explained simply: from the XOR gate to binary addition
Your phone does billions of additions a second, yet it only knows 0 and 1. How does it manage? With two logic gates, an XOR and an AND, wired side by side. Here is the adder, step by step, with its diagram.
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Counting with only 0 and 1
We count in base ten: ten digits, from 0 to 9, and when we go past 9, we write a 1 in the tens column. A computer counts in base two, or binary: just two digits, 0 and 1. When it goes past 1, it moves on to the next column. So two is written 10, three 11, four 100, five 101, six 110. Each column is worth double the one to its right: 1, 2, 4, 8, 16…
A binary digit is called a bit. That is perfect for a circuit: a wire either carries a voltage (1) or it does not (0).
Adding two bits: only four cases
Adding two bits, A and B, gives only four cases. 0 + 0 = 0. 0 + 1 = 1. 1 + 0 = 1. And 1 + 1 = 2, which is written 10 in binary: you write down 0 and carry 1, exactly as 5 + 7 = 12 in base ten, where you write down 2 and carry 1.
So the result has two digits: the sum S, the digit you write down, and the carry C, the one you take to the next column. In the truth table, S is 0, 1, 1, 0 and C is 0, 0, 0, 1.
The sum is an XOR gate
Look at the S column: it is 1 when A and B are different, and 0 when they are the same. That is exactly the rule of the XOR gate (exclusive OR), the one behind a two-way light switch on a staircase. Our page on the XOR gate covers it in detail, with a circuit to play.
The carry is an AND gate
The C column is only 1 on the last row, when A and B are both 1: that is the AND gate. So all you need is to wire A and B into two gates at once, an XOR and an AND, and you have a half adder, the one in the diagram. Two gates, and the machine can do 1 + 1.
You can check it yourself: the last of the 10 free circuits of our game, called “The half adder”, asks you to place the gate for the sum.
Why “half”?
Because something is missing. From the second column of a sum onwards, you have to add three bits: the one from A, the one from B, and the carry coming in from the column on the right. So the full adder has three inputs: A, B and the carry-in.
Its sum takes two XOR gates in a row: A XOR B, then that result XOR the carry-in. Its carry-out is 1 as soon as at least two of the three bits are 1. That “at least two out of three” is a majority vote, and it happens to be the second-to-last free circuit, “Majority vote”: three AND gates and two OR gates. Anyone who has solved it has built the carry of an adder without knowing it.
A complete sum, column by column
Let's add 5 and 3. In binary, 5 is 101 and 3 is 011. Right-hand column: 1 + 1 = 10, write down 0, carry 1. Middle column: 0 + 1 + the carried 1 = 10, write down 0, carry 1. Left-hand column: 1 + 0 + 1 = 10, write down 0, carry 1. The last carry becomes the first digit: 1000, which is 8. Correct.
A circuit does the same thing: one adder per column, with each carry wired into the next adder. This is called a ripple-carry adder. To add two 64-bit numbers you could line up 64 of them; real processors use faster designs, but this is where the idea starts.
What next?
With addition you can subtract (thanks to a clever way of writing negative numbers, called two's complement), multiply (shifted additions) and do almost all the arithmetic a computer does. It all starts with two gates that a student can place in a minute.
For the classroom, the “XOR and the adder” lesson in our Teacher Pack (€15) has students work out the sum and the carry by hand, then check them on projected circuits.