Adding with Logic Gates: The Half Adder as a Puzzle
Hiroki Obara · DeveloperMath GatesHow-To
In AND, OR and NOT as Puzzles, I wrote about the three operations that combine and flip true and false. This post continues from there. Computers add numbers using only those three operations, and the smallest part that does it is called a half adder.
The name sounds technical, but inside it there are only two tables of four rows each. I hope you can read this as a puzzle.
Adding in binary
Inside a computer, numbers are written with only 0 and 1. This is called binary. In the decimal numbers we use every day, a new digit starts after 9, giving 10. In binary, a new digit starts after 1.
| Decimal | Binary |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
Adding two one-digit binary numbers has only four cases.
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 10
Only 1 + 1 gives a two-digit answer. It is the same as 5 + 5 = 10 in decimal: a 0 stays in that place, and a 1 is carried to the next place.
Splitting the answer in two
Let us split the answer into the digit that stays, the sum, and the digit sent to the next place, the carry.
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Now read 1 as true and 0 as false. If you compare this with the truth tables in the last post, something stands out.
The carry column is 1 only when both A and B are 1. That is exactly AND.
The sum column is 1 when exactly one of A and B is 1, and 0 when both are. That looks like OR, except for the last row. It is XOR, exclusive or, which I only named at the end of the last post.
So adding one binary digit comes down to “the sum is XOR, the carry is AND”. A circuit that combines the two is a half adder.
Building XOR from AND, OR and NOT
XOR can be built from AND, OR and NOT. This is the puzzle of this post.
XOR means “at least one is true” and “not both are true”. Turning those words straight into a formula gives this.
Sum = (A OR B) AND NOT (A AND B)
Let us check it with a table.
| A | B | A OR B | A AND B | NOT (A AND B) | Sum |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
The last column matches the sum column above. And the “A AND B” we used along the way is the carry itself. So a half adder can be built from one AND, one OR, one NOT and one more AND.
You can also think of it with the switch and light bulb circuits from the last post. Switches in series were AND, and switches in parallel were OR. A half adder is a set of such switches arranged so that, for 1 + 1, the sum bulb goes off and the carry bulb comes on.
Why “half”?
A half adder can only add one digit to one digit. When you add numbers with two or more digits, you also have to add the 1 carried up from the place below. A circuit that adds three one-digit values is called a full adder. A full adder can be made from two half adders and one OR. Add A and B, add the carry from below to that sum, and if either half adder produced a carry, send a 1 to the next place.
Put one full adder for each place in a row, pass each carry to its neighbour, and you can add numbers of any length. For binary 11 + 01 (decimal 3 + 1), the first place is 1 + 1, giving sum 0 and carry 1. The second place is 1 + 0 + 1, again sum 0 and carry 1. A 1 comes out in the third place, and the answer is 100, decimal 4.
This is exactly what carrying does in column addition. The only difference is that there are just two digits, 0 and 1.
If you want to see the circuit diagrams, the English Wikipedia article on the adder has them for both half and full adders.
Seen as remainder and quotient
You can also say it in the language of arithmetic. If you divide A + B by 2, the sum is the remainder and the carry is the quotient. 1 + 1 = 2, and 2 divided by 2 is quotient 1, remainder 0. That is the last row of the table.
I think this view is worth knowing. A half adder is a logic device, and at the same time it is a device that adds, divides by 2, and splits the result into remainder and quotient. Logic and arithmetic are not separate subjects here. They are two ways of writing the same thing, and I think the half adder shows that very clearly.
Circuit puzzles to try at home
With just paper and a pencil, you can make problems like these.
- Using only AND, OR and NOT, write a formula that is true only when A and B are the same (it is XOR flipped with NOT)
- Using two half adders, write out the table for a full adder (eight rows)
- Work out binary 101 + 011 one place at a time, as if three full adders were lined up
For the first one, once you have a formula, write the four-row truth table to check it. If the formula is right, the columns come out the way you expect. If not, the row where they disagree shows you where you mixed up AND and OR.
The logic world in Math Gates
Math Gates is a circuit puzzle game I make. You place gates that change numbers and mirrors that turn the path 90 degrees on the empty squares of a board, press Run, and a bit carrying a number moves in a straight line. The destination port accepts only values that meet its condition.
In the last world, Logic Circuit, a number that passes a comparison gate turns into true or false and then goes through NOT, AND and OR gates. A logic gate shows the truth value it combines with, as in “AND T”, and combines it with the bit’s own value. Only one bit runs across the board, so you cannot build a half adder itself, which needs two inputs at once. Still, you can check again and again, through the way the bit runs, that AND is strict, OR is loose and NOT flips. World 3, Remainder Circuit, also has remainder gates, which connect with the “remainder when divided by 2” idea in this post.
There are 140 puzzles across seven worlds, aimed at ages 8 and up. It is free to play with ads between puzzles, and a one-time purchase removes the ads. How to play is in Getting Started with Math Gates.
