Digital Systems
3 min read
Half and full adders
A half adder adds two bits with one XOR gate for the sum and one AND gate for the carry. A full adder also takes a carry in, and chaining one per bit gives the adder at the heart of every CPU's arithmetic logic unit.
Half adder: two bits
Adding two single bits gives a sum bit and a carry bit: 0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01 and 1 + 1 = 10. The sum column is exactly XOR, and the carry column is exactly AND. So a half adder is two gates:
sum = a ^ b; // 1 when exactly one input is 1
carry = a & b; // 1 only when both are 1Full adder: a carry in
Every column except the lowest also receives the carry from the column below. A full adder adds three bits: A, B and the carry in, Cin. The sum is A xor B xor Cin. The carry out is 1 when at least two of the three inputs are 1. It can be built from two half adders and an OR gate: the first half adder adds A and B, the second adds its sum to Cin, and the OR combines the two carries.
| A | B | Cin | Sum, Cout |
|---|---|---|---|
| 0 | 1 | 0 | 1, 0 |
| 1 | 1 | 0 | 0, 1 |
| 1 | 0 | 1 | 0, 1 |
| 1 | 1 | 1 | 1, 1 |
Chain them: the ripple-carry adder
To add two 4-bit numbers, use four full adders, one per bit, and connect each carry out to the next carry in. For 0110 + 0011 the carries ripple upward and the result is 1001, which is 9. The first adder has Cin = 0, or 1 when the same circuit is used for subtraction with an inverted second input.
The weakness is delay: the top bit has to wait for the carry to ripple through every lower bit, so a longer adder is slower. Faster designs, such as carry-lookahead, compute the carries in parallel at the price of more gates. Your CPU's adder uses such tricks, which is why a 32-bit add can still finish in one clock cycle.