How gates add numbers

One XOR and one AND gate are enough to add two bits. Chain four full adders and you can add any two numbers from 0 to 15.

Try this before reading on. Add 0101 and 0011 on paper, in binary, the way you add in decimal, and write each carry above the next column. You need only three facts: 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10, which means write 0 and carry 1. With a carry coming in, 1 + 1 + 1 = 11, so you write 1 and carry 1. The working is in the next paragraph, so cover it up first.

Here is the working. Rightmost column: 1 + 1 = 10, write 0, carry 1. Next: 0 + 1 plus the carry is 10 again, write 0, carry 1. Next: 1 + 0 plus the carry, 10, write 0, carry 1. Leftmost: 0 + 0 plus the carry is 1. The answer is 1000, which is 8, and 5 + 3 = 8. Three of the four columns carried. A calculator, a game and a spreadsheet all end up doing exactly this. Inside a processor each column is handled by a few gates, and the scene starts on the same sum. Then try 9 + 8 there. It needs a fifth bit.

The rightmost column needs only two gates

Look at the rightmost column on its own. The answer bit there, the sum, is 1 when exactly one input is 1. That is the XOR rule. The carry is 1 only when both inputs are 1. That is the AND rule. So an XOR gate and an AND gate side by side, fed the same two inputs, add two bits. This little circuit is a half adder. It is only "half" because it has no way to take in a carry from a column to its right.

The other columns have three bits to add

In every other column three bits meet: one from each number and the carry from the right. A full adder takes all three. Its sum is A XOR B XOR carry-in, which is 1 when an odd number of the three are 1. Its carry-out is 1 when at least two of them are 1. Two half adders and an OR gate make one full adder. Line up four full adders, wire each carry-out to the carry-in of the adder on its left, and you have a 4-bit adder. Each carry has to ripple from right to left before the last column settles, so this design is called a ripple-carry adder. Real processors add 64-bit numbers with cleverer circuits that work out the carries ahead of time, but the rule in each column is the same.

What happens when the answer is too big

Four bits hold 0 to 15. Add 9 and 8 and the true answer, 17, is 10001 in binary, which is five bits. A register that keeps only four bits stores 0001, which is 1, and the carry left over on the left is the warning sign. That is overflow. 15 + 1 in four bits leaves 0000. Processors set a flag when it happens so that programs can notice. Subtraction reuses the same adder. To work out A − B, the processor flips every bit of B and adds 1, which gives the two's complement of B, then adds that to A and drops the extra carry. For 5 − 3 in four bits: 3 is 0011, flipped it is 1100, plus 1 it is 1101. Then 0101 + 1101 = 10010, and keeping four bits leaves 0010, which is 2.

Multiplying is shifting and adding

Multiplication comes from the same parts. In binary, multiplying by 2 moves every bit one place to the left, just as multiplying by 10 adds a zero in decimal: 0011 (3) becomes 0110 (6). For 5 × 3, notice that 3 is 2 + 1. So 5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111, which is 15. A multiplier circuit shifts and adds like this, taking the 1 bits of the second number one at a time.