Introduction
Computers add numbers with circuits built from additions of single binary digits. The circuit that does one of those additions uses nothing but "and," "or," and "not." This reading builds it from a truth table, then shows how copies of it chain together to add longer numbers.
The Starting Point
You have two one-digit binary numbers, A and B. A binary number is written in base two, using only the digits 0 and 1. Each of A and B is therefore either 0 or 1. The task is to design a circuit whose outputs give A + B.
The building blocks are logic gates: small components that take bits (values of 1 or 0) as inputs and produce an output bit by a fixed rule.
- An AND gate outputs 1 only when both inputs are 1.
- An OR gate outputs 1 when at least one input is 1, including when both are.
- A NOT gate flips its single input: 0 becomes 1 and 1 becomes 0.
These rules come from Boolean algebra, the algebra of true and false named after George Boole, who treated logic as algebra in 1854 (O'Connor and Robertson 2004). Reading 1 as true and 0 as false turns every logical rule into a rule about bits. In 1938, Claude Shannon showed that switching circuits follow this algebra, and among his examples was a circuit that adds numbers in base two (Shannon 1938).
Walking Through the Circuit Design
Step 1: List all four cases
Two inputs, each 0 or 1, give four cases. Write each one out in ordinary arithmetic first:
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 2
Listing every case is the same move as writing a truth table: if the circuit gets all four right, it's right for every possible input. There's nothing else it could be asked.
Step 2: Separate the answer into a sum digit and a carry digit
The answers have to be written in binary too. The first three are fine: 0 and 1 are single binary digits. But 2 in binary is written 10, meaning one two and no ones, just as ten in ordinary notation is written 10, meaning one ten and no ones.
So every answer needs two output digits. The sum digit is the ones place. The carry digit is the twos place, the digit that carries into the next column. Here is the full table:
| A | B | A + B | Carry | Sum |
|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 (binary 10) | 1 | 0 |
Check each row: carry times 2 plus sum gives A + B. In the last row, 1 \times 2 + 0 = 2.
Step 3: Recognize the two outputs as logical operations
Look at each output column as a truth table on its own.
The carry column reads 0, 0, 0, 1. It's 1 only when both A and B are 1. That is exactly the AND gate's table. So the carry is A AND B.
The sum column reads 0, 1, 1, 0. It's 1 when exactly one of A and B is 1, and 0 when they're the same. That operation has its own name: exclusive or, often shortened to XOR. It means "one or the other, but not both." Compare it with the OR gate, which outputs 1 in the last row as well. The two differ only when both inputs are 1.
Step 4: Build exclusive or from AND, OR, and NOT
The sum needs an exclusive or, but the toolkit has only AND, OR, and NOT. Put the meaning into words: "one or the other, and not both." Each word is a gate.
- "One or the other" is A OR B.
- "Both" is A AND B.
- "Not both" is NOT (A AND B).
- Join the first and third with AND.
So the sum is (A OR B) AND NOT (A AND B). Check it against the four cases:
| A | B | A OR B | A AND B | NOT (A AND B) | Sum |
|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
The last column matches the sum column from Step 2. Notice that the AND gate computing "both" is also the carry, so one gate serves two purposes. The finished circuit, called a half adder, uses four gates: one OR, one AND, one NOT, and a second AND.
Step 5: Chain adders to add longer binary numbers
Longer numbers are added column by column, right to left, exactly as you add on paper. Every column after the first has three bits to add: a digit from each number and a carry from the column to its right. A circuit that handles three input bits is called a full adder. One way to build it is from two half adders: add the two digits, add the carry to that result, and combine the two carry outputs with an OR gate.
Take 6 + 3. In binary, 6 is 0110 and 3 is 0011. Working from the right:
| Column | Digits | Carry in | Sum digit | Carry out |
|---|
| Ones | 0 and 1 | 0 | 1 | 0 |
| Twos | 1 and 1 | 0 | 0 | 1 |
| Fours | 1 and 0 | 1 | 0 | 1 |
| Eights | 0 and 0 | 1 | 1 | 0 |
Read the sum digits from the bottom row up: 1001. That's one eight and one one, which is 9. Each carry out feeds the next column's carry in. Chain 64 of these adders and you can add 64-digit binary numbers.
Key Considerations
Binary 1 + 1. In binary, 1 + 1 is written 10 and read "one-zero," meaning two. The circuit reports it as sum 0, carry 1. Writing the sum as "2" is impossible, because a single bit can only be 0 or 1. That's why the carry exists.
The common mistake: treating "or" as "exactly one." In everyday speech, "coffee or tea" usually means one or the other, not both. Logical "or," and the OR gate, include both: they output 1 when both inputs are 1. If you build the sum with a plain OR gate, the circuit gets the first three cases right and the last one wrong, reporting a sum digit of 1 for 1 + 1. The fix is the extra "and not both" from Step 4.
Terminology. "Exclusive or" and "XOR" are the same operation. Engineers often draw it as a single gate, but inside it is built from simpler gates like the ones above.
Summary
Adding two binary digits produces a sum digit and a carry digit. The carry is AND; the sum is exclusive or, built from OR, AND, and NOT. Here is the finished half adder:
| A | B | Carry (A AND B) | Sum ((A OR B) AND NOT (A AND B)) |
|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Gate diagram in words: inputs A and B each feed both an OR gate and an AND gate. The AND gate's output is the carry. It also feeds a NOT gate. The OR gate's output and the NOT gate's output feed a second AND gate, whose output is the sum.
- Check every row: carry times 2 plus sum equals A + B.
- The single shared AND gate gives the carry and also supplies "both" for the sum.
- Two half adders and an OR gate make a full adder; a chain of full adders adds numbers of any length, as in 0110 + 0011 = 1001 (6 + 3 = 9).
References
- O'Connor, J. J., and E. F. Robertson. 2004. "George Boole." MacTutor History of Mathematics Archive, University of St Andrews. Last updated June 2004.
- Shannon, Claude E. 1938. "A Symbolic Analysis of Relay and Switching Circuits." Transactions of the American Institute of Electrical Engineers 57: 713–723.
- Free: None confirmed
- Free companion: O'Connor and Robertson 2004