Half adders and full adders
Adding two one-bit numbers has four cases: 0+0=0, 0+1=1, 1+0=1 and 1+1=10 (that is "two" in binary: a 0 with a carry of 1). Two output bits are needed, and each one is a gate you already know.
The half adder
| A | B | SUM | CARRY |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
The SUM column is exactly XOR and the CARRY column is exactly AND. So a half adder is two gates: SUM = A XOR B, CARRY = A AND B. It is called "half" because it cannot accept a carry coming in from a previous column.
Try it: the simulator's half adder example is this circuit. Flip the switches and watch the truth table row highlight. Then do practice puzzle 3 from memory.
The full adder
When you add multi-digit numbers by hand you carry a 1 into the next column. A full adder takes three inputs, A, B and the carry-in CIN, and produces SUM and COUT. The trick is to add in two stages:
- Half-add A and B:
S1 = A XOR B,C1 = A AND B. - Half-add S1 and CIN:
SUM = S1 XOR CIN,C2 = S1 AND CIN. - A carry comes out if either stage carried:
COUT = C1 OR C2.
That is five gates, two XOR, two AND, one OR, and the standard textbook circuit. Notice that A XOR B is computed once and used twice; reusing signals is how you beat the par in Gatesmith puzzles.
| A | B | CIN | SUM | COUT |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Two patterns are worth memorizing: SUM is 1 when an odd number of inputs are 1 (it is three-way XOR), and COUT is 1 when at least two inputs are 1 (it is the majority function from practice puzzle 4).
Try it: Practice puzzle 6, "Full Adder". Five gates is the best known.
From one bit to a number
To add two 8-bit numbers, line up eight full adders and feed each COUT into the next CIN. This is a ripple-carry adder: simple, but the carry has to travel through every stage before the top bit is final, which limits speed. Real processors use carry-lookahead and other tricks to compute carries in parallel, but they all start from the full adder you just built. In the simulator you can save your full adder as a module and place eight copies to try it.