Full adder
How a computer really adds
A full adder adds three bits, two operands plus a carry-in, producing a Sum and a carry-out. Chaining one full adder per bit position is exactly how a CPU adds multi-bit numbers.
Build it in the lab →The half adder adds the rightmost column of a binary sum, where there is no carry coming in. Every other column receives a carry from its right, so it must add three bits. This lesson extends the half adder to take that third input, and the result is the real workhorse of computer arithmetic. Watch that column-by-column addition, with its rippling carry, in the interactive binary addition walkthrough.
The three inputs are
A, B, and CIN (carry-in). The two outputs are the sum S and the carry-out COUT, which feeds the next column to the left. The binary calculator shows that carry chain running across a whole addition.| A | B | CIN | S | 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 |
S is 1 when that count is odd, COUT is 1 when it is 2 or 3.Clean way to see it:
S is the low bit of *how many inputs are 1*, and COUT is the high bit of that same count. Three one-bit inputs sum to 0, 1, 2, or 3, a two-bit number, and COUT,S together spell exactly that count in binary.Building from two half adders and an OR
You already have the half adder saved. A full adder is two of them plus one OR. The first half adder adds
A and B; the second folds in CIN. Each can produce a carry, and the two carries are merged with OR. They are never both 1 at once, which is exactly why a plain OR is enough.- Place two half adder parts (HA1 and HA2) and one OR part.
- Feed
AandBinto HA1. It produces a partial sumPand a carryC1. - Feed
PandCINinto HA2. It produces the final sumSand a carryC2. - Feed
C1andC2into the OR gate. Its output isCOUT. - Label the outputs: HA2's sum is
S, the OR output isCOUT.
S = A ⊕ B ⊕ CIN
COUT = 1 when at least two of A, B, CIN are 1
C1 and C2 are never both 1, so OR safely merges them into COUT. Open it in the lab and step through all eight rows.Try it
Set
A = 1, B = 1, CIN = 1 on the full adder. What are S and COUT? (Hint: three 1s sum to 3, a 2-bit number.)Answer
All three inputs
1 sum to 3, which is 11 in binary. So COUT = 1 (the high bit) and S = 1 (the low bit). Read COUT,S = 1,1. This is why S is the low bit of the count of 1s and COUT is the high bit: together they spell how many inputs are 1.Now the payoff. Line up eight full adders in a row, wire each
COUT into the CIN to its left, and tie the rightmost CIN to 0. That chain adds two 8-bit numbers in one shot. It is called a ripple-carry adder, and it is the arithmetic core of the ALU you will build for your CPU. (The only cost of width is delay: the carry must ripple through every stage before the top sum settles.)One more reason this block is central: with a controllable inverter on one input (the XOR trick from the XOR lesson), the very same adder can subtract. Add becomes subtract by flipping one number's bits and carrying in a 1. Your CPU gets addition and subtraction from one piece of hardware.
Counting how many inputs are 1: a vote counter
Here is a second, less obvious job for this block. Picture a panel of five judges, each with a button. You do not care *who* pressed, only *how many* pressed, a count from 0 to 5 that needs 3 bits. The clumsy route is a 32-row truth table. The elegant route reuses the full adder, because a full adder already counts: as noted above,
COUT,S spells how many of its three inputs are 1 as a 2-bit number. Feed three buttons into one full adder and it reports 0, 1, 2, or 3. That is the whole idea.With five buttons
X1 through X5, one full adder is not enough, so cascade a few: group the first three, fold in the last two, then combine the carries.- FA1 adds
X1 + X2 + X3. Its sumA0has weight 1 (the ones place); its carryA1has weight 2 (the twos place). - FA2 adds the two remaining buttons plus that partial sum:
X4 + X5 + A0. Its sumQ0is the final ones bit; its carryB1also has weight 2. - A half adder adds the two weight-2 carries
A1 + B1. Its sumQ1is the twos bit; its carryQ2is the fours bit. - Read the 3-bit count off
Q2 Q1 Q0. Two full adders and one half adder count five inputs.
The pattern has a name: a full adder used this way is a 3-to-2 compressor. It swallows three bits of the same weight and emits two bits, a sum in that column and a carry in the next column to the left. Stack compressors and combine their carries and you can total *any* number of one-bit inputs. This is the beating heart of fast multipliers, where dozens of partial-product bits get crushed down a compressor tree.
Scale the panel to fifteen judges and nothing changes but the size. Fifteen buttons can sum to anywhere from 0 to 15, a 4-bit count
Q3 Q2 Q1 Q0. Build it as a compressor tree: full adders in the first layer squeeze groups of three buttons into sums and carries, the next layer squeezes those, and so on until each weight column holds a single bit.There is a tidy way to know the size in advance. Every full adder takes in three bits and puts out two, so it removes exactly one bit from the pile; a half adder (two in, two out) removes none. You start with 15 live bits and must end with 4, so the tree needs exactly eleven full adders no matter how you arrange them, plus however many half adders you need to line up bits that pile into the same column.
Two things bite here. First, weight matters: a carry always feeds the column one place to the left, so never merge a sum bit with a carry bit of a different weight. Second, depth costs time. Each layer of adders can only settle after the layer feeding it has settled, so a tall tree has a long worst-case delay, the same ripple problem as the multi-bit adder above. Keep the tree balanced (short and bushy rather than tall and thin) to hold the delay down.
For a small number of inputs there is a shortcut: skip the adders and use a lookup table. Wire the input bits as the address of a ROM whose stored word at each address is the precomputed count. Five inputs need only a 32-entry table (
2^5), each holding a 3-bit number. But the table doubles with every added input, so fifteen inputs would need a 32768-entry ROM (2^15). A lookup wins for a handful of inputs; the compressor tree wins once there are many.Try it
On the five-input vote counter, four of the five judges press (say
X1 = X2 = X3 = X4 = 1, X5 = 0). Trace A0, A1, Q0, B1, Q1, Q2 and read the 3-bit count.Answer
FA1 adds
X1 + X2 + X3 = 1 + 1 + 1 = 3, so A0 = 1 and A1 = 1. FA2 adds X4 + X5 + A0 = 1 + 0 + 1 = 2, so Q0 = 0 and B1 = 1. The half adder adds A1 + B1 = 1 + 1 = 2, so Q1 = 0 and Q2 = 1. The count is Q2 Q1 Q0 = 100, which is 4. Four buttons, count of four.Frequently asked
What is a full adder?
A full adder adds three bits, two operands
A and B plus a carry-in CIN, and produces a Sum S and a carry-out COUT. The carry-out feeds the next column to the left.How is a full adder built from half adders?
From two half adders and one OR gate. The first half adder adds
A and B; the second folds in CIN. Each can raise a carry, and since they are never both 1 at once, an OR safely merges the two carries into COUT.How do full adders add multi-bit numbers?
Line up one full adder per bit position and wire each
COUT into the CIN of the next adder to the left, tying the rightmost CIN to 0. That chain is a ripple-carry adder, and it is the arithmetic core of a CPU's ALU.What is the difference between a half adder and a full adder?
A half adder adds only two bits and cannot accept a carry-in, so it works only for the rightmost column. A full adder adds three bits (including a carry-in), so it works for every column and can be chained.
How do you count how many bits are 1 (a population count)?
Feed the bits into a tree of full adders. A full adder reports how many of its three inputs are
1 as a 2-bit number, so it acts as a 3-to-2 compressor; stacking compressors and combining their carries totals any number of one-bit inputs. Counting five inputs takes two full adders and one half adder and yields a 3-bit count, and the same pattern scales to a 4-bit count for fifteen inputs.What is a compressor tree?
A compressor tree is a layered arrangement of full and half adders that reduces many bits of the same weight down to one final sum. Each full adder removes exactly one bit (three in, two out), so counting fifteen one-bit inputs into a 4-bit total takes exactly eleven full adders. Keeping the tree balanced holds the number of layers, and therefore the propagation delay, low.
When should you use a ROM lookup instead of an adder tree to count bits?
Use a ROM lookup when there are only a few inputs. Wire the inputs as an address into a ROM that stores the precomputed count at each entry: five inputs need just a 32-entry table. Because the table doubles with every added input (fifteen would need 32768 entries), a compressor tree of full adders is the better choice once there are many inputs.
You've got the theory. Now build it from scratch and watch it work.
Build it in the lab →