# 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.

Group: Arithmetic
URL: https://digiwleea.wleeaf.dev/learn/fulladder/

The [half adder](https://digiwleea.wleeaf.dev/learn/halfadder/) 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](https://digiwleea.wleeaf.dev/tools/binary-addition/).

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](https://digiwleea.wleeaf.dev/tools/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 |

_Full adder truth table. Count the 1s in each row: S is 1 when that count is odd, COUT is 1 when it is 2 or 3._

> **KEY:** 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](https://digiwleea.wleeaf.dev/learn/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.

1. Place two half adder parts (HA1 and HA2) and one OR part.
2. Feed `A` and `B` into HA1. It produces a partial sum `P` and a carry `C1`.
3. Feed `P` and `CIN` into HA2. It produces the final sum `S` and a carry `C2`.
4. Feed `C1` and `C2` into the OR gate. Its output is `COUT`.
5. Label the outputs: HA2's sum is `S`, the OR output is `COUT`.

```
S = A XOR B XOR CIN
```

```
COUT = 1 when at least two of A, B, CIN are 1
```

_Circuit diagram: Full adder from two half adders and one OR. 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._

**Q (Try it):** Set `A = 1, B = 1, CIN = 1` on the full adder. What are `S` and `COUT`? (Hint: three `1`s sum to 3, a 2-bit number.)

**A:** 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 `1`s and `COUT` is the high bit: together they spell how many inputs are `1`.

> **KEY:** 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.)

> **TIP:** One more reason this block is central: with a controllable inverter on one input (the XOR trick from the [XOR](https://digiwleea.wleeaf.dev/learn/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.

1. FA1 adds `X1 + X2 + X3`. Its sum `A0` has weight 1 (the ones place); its carry `A1` has weight 2 (the twos place).
2. FA2 adds the two remaining buttons plus that partial sum: `X4 + X5 + A0`. Its sum `Q0` is the final ones bit; its carry `B1` also has weight 2.
3. A [half adder](https://digiwleea.wleeaf.dev/learn/halfadder/) adds the two weight-2 carries `A1 + B1`. Its sum `Q1` is the twos bit; its carry `Q2` is the fours bit.
4. Read the 3-bit count off `Q2 Q1 Q0`. Two full adders and one half adder count five inputs.

> **KEY:** 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.

> **KEY:** 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.

> **WARN:** 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.

> **TIP:** 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.

**Q (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.

**A:** 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.

### FAQ

**Q:** What is a full adder?

**A:** 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.

**Q:** How is a full adder built from half adders?

**A:** From two [half adders](https://digiwleea.wleeaf.dev/learn/halfadder/) and one [OR](https://digiwleea.wleeaf.dev/learn/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`.

**Q:** How do full adders add multi-bit numbers?

**A:** 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](https://digiwleea.wleeaf.dev/learn/alu/).

**Q:** What is the difference between a half adder and a full adder?

**A:** A [half adder](https://digiwleea.wleeaf.dev/learn/halfadder/) 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.

**Q:** How do you count how many bits are 1 (a population count)?

**A:** 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](https://digiwleea.wleeaf.dev/learn/halfadder/) and yields a 3-bit count, and the same pattern scales to a 4-bit count for fifteen inputs.

**Q:** What is a compressor tree?

**A:** 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.

**Q:** When should you use a ROM lookup instead of an adder tree to count bits?

**A:** 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.