Half and full adders
Add two bits the way you add on paper, and you get a sum bit and a carry bit. The sum is XOR and the carry is AND: that pair of gates is a half adder. Add a third bit, the carry coming in from the next column, and you need a full adder: two half adders and an OR gate. Step through all 8 rows of its truth table with lamps.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01In binary, what is 1 + 1?
A binary column holds only 0 or 1. Two is written 10: a 0 stays in the column (the sum) and a 1 moves one column left (the carry).
02Which gate gives the sum bit of a half adder?
The sum is 1 when exactly one input is 1 and 0 when the inputs match. That is XOR: S = A XOR B.
03Why is it called a half adder?
A half adder adds just two bits. To add longer numbers, each column also has to add the carry from the column to its right, which needs a full adder.
04A full adder gets A = 1, B = 1 and Cin = 1. What are Cout and S?
1 + 1 + 1 = 3, which is 11 in binary: Cout = 1 and S = 1. Check: S = 1 XOR 1 XOR 1 = 1, and Cout = (1 AND 1) OR (1 AND 0) = 1.
05A full adder joins the carries of its two half adders with an OR gate. Why is OR enough?
The first carry is 1 only when A and B are both 1, and then P = A XOR B is 0, so the second carry (Cin AND P) is 0. At most one is 1, and OR passes it on.
Glossary
- Bit
- One binary digit: 0 or 1. In a circuit, a low or a high voltage; here a dark or a glowing lamp.
- Carry
- The bit that moves one column to the left when a column's sum is too big for one digit, as in 1 + 1 = 10.
- XOR (exclusive OR)
- A gate whose output is 1 when its two inputs are different and 0 when they are the same.
- Half adder
- An XOR gate and an AND gate that add two bits, giving a sum S = A XOR B and a carry C = A AND B.
- Full adder
- A circuit that adds three bits (A, B and a carry in) and gives a sum and a carry out; two half adders and an OR gate.
- Carry in (Cin)
- The carry arriving from the column to the right, added in along with A and B.
- Carry out (Cout)
- The carry a full adder sends on to the column to its left.
- Truth table
- A list of every combination of input bits and the outputs each one gives.
Notes and sources
- In binary each column is worth twice the one to its right, so 10 means one two and no ones: 2. A sum that does not fit in one column sends a carry left, just like 9 + 1 = 10 in decimal.
- A half adder is one XOR gate (sum) and one AND gate (carry). A full adder is two half adders and one OR gate: S = A XOR B XOR Cin and Cout = (A AND B) OR (Cin AND (A XOR B)), which is the same as AB + ACin + BCin (Harris and Harris, Digital Design and Computer Architecture, section 5.2.1).
- The two carries can never both be 1: the first is 1 only when A = B = 1, and then P = A XOR B = 0, so the second is 0. That is why a plain OR is enough to join them.
- Chain full adders, each Cout wired to the next column's Cin, and they add numbers of any length; this chain is called a ripple-carry adder. Texas Instruments' SN74LS283 chip adds two 4-bit numbers plus a carry in, using a faster look-ahead carry inside.
- In Python, ^, & and | on the numbers 0 and 1 work as XOR, AND and OR, so s = a ^ b ^ cin and cout = (a & b) | (cin & (a ^ b)) give the same 8 rows as the circuit.
- Harris and Harris, Digital Design and Computer Architecture (section 5.2.1: half adder, full adder, carry propagate adders)
- Nisan and Schocken, The Elements of Computing Systems, project 2: Boolean arithmetic (HalfAdder, FullAdder)
- MIT OpenCourseWare 6.004 Computation Structures
- Texas Instruments SN74LS283 4-bit binary full adder datasheet
- Python reference: binary bitwise operations (&, ^, |)
Quiz Unlocks after the last step.