Adding With Nothing but Switches
Your phone adds numbers billions of times a second, and nothing inside it knows what a number is. The chip inside is packed with tiny switches: about 19 billion in an iPhone 15 Pro, by Apple's count. Each switch can only be on or off.
So how does a crowd of on/off switches work out 6 + 7? In 1937, a Bell Labs engineer named George Stibitz took two spare telephone switches home and built an adding machine on his kitchen table, with flashlight bulbs to show the answer. The machine became known as the Model K: K for kitchen.
Make your guess. A light switch shows one of two things: on or off. How many switches do you need to show every whole number from 0 to 1,000?
- About 1,000
- About 100
- 10
Show answer
C. 10
Ten switches are enough. Each extra switch doubles the number of on/off patterns: 2, 4, 8, 16, and so on. Ten switches make 1,024 patterns, enough for every number from 0 to 1,023. The trick is a way of writing numbers with only two digits.
Start with the switches themselves. How can a row of switches that only know on and off hold a number like 13?
Count on switches
Everyday numbers use ten digits, and each place is worth ten times the place to its right: ones, tens, hundreds. Switches have only two settings, so a computer counts in binary: 0 for off, 1 for on. In binary, each place is worth twice the place to its right: 1, 2, 4, 8.
To read a row of switches, add the place values of the switches that are on. A switch that is off adds nothing.
Your goal: flip the switches to make each number the widget asks for. Then press Add 1 a few times and watch which switches flip.
Adding 1 to 7 flips four switches at once: 0111 becomes 1000. The ones place can't hold a 2, so the ones switch resets to 0 and passes a 1 to the next place. That pass is the same carry you make when 9 + 1 becomes 10. In binary, 1 + 1 = 10.
So a computer adds with the method you learned in school, using only 0 and 1. But a switch can't read digits or follow a method. How can switches decide anything?
Switches that decide
Also in 1937, a 21-year-old MIT student named Claude Shannon wrote a master's thesis with a simple-sounding idea: wires and switches can do logic. Put two switches in a row, and a lamp lights only if switch A and switch B are on. Put two switches side by side, and the lamp lights if switch A or switch B is on.
A circuit like these, with on/off inputs and one on/off output, is called a logic gate. Adding needs a third gate, called XOR (exclusive or): the XOR output is on when exactly one input is on.
You have probably used an XOR gate already. A stairway light with one switch at the bottom and one at the top changes whenever you flip either switch.
Your goal: flip A and B through all four combinations, and compare the three lamps with the answer to A + B at the bottom.
Which gate's lamp always matches the right digit of A + B?
- AND
- OR
- XOR
Show answer
C. XOR
XOR. The right digit is 1 when exactly one input is on (0 + 1 = 01) and 0 when both inputs are on (1 + 1 = 10). That is the XOR rule. The left digit is 1 only when both inputs are on: the AND rule. OR gets 1 + 1 wrong, because the OR lamp lights while the right digit is 0.
So two gates side by side add two binary digits. XOR gives the sum digit, and AND gives the carry. Engineers call this pair a half adder.
Why only half? Picture a column in the middle of a long sum. How many digits does that column have to add?
Carry the one
Every column except the rightmost one can receive a carry, so a column has to add three digits, not two. A half adder has only two inputs.
The fix is two half adders. The first half adder adds the top and bottom digits, and the second adds the carry to that result. Either half adder can make a carry, so an OR gate joins the two carries. The whole circuit is a full adder: five gates that add one column.
Your goal: turn on all three inputs, then read the two output lamps together as one binary number.
With all three inputs on, both lamps light: carry out 1 and sum 1, which is binary 11, or 3. One full adder adds one column. What happens when four full adders work side by side?
Add two numbers
To add whole numbers, a chip lines up one full adder per column. The carry out of each adder becomes the carry in of the adder to its left. A carry can then travel, or ripple, from the right end to the left end. Engineers call this chain a ripple-carry adder.
Your goal: flip the switches to make 15 on top and 1 on the bottom, and watch the carry ripple from right to left.
15 + 1 = 16 needs the fifth lamp. A computer that keeps only four digits drops that last carry and shows 0. The mistake is called overflow.
Overflow happens at full size too. In 2014, YouTube said the view count of the music video Gangnam Style was nearing 2,147,483,647, the largest number its counter could hold, so YouTube moved the counter to 64 bits.
A 64-bit computer adds two binary numbers with 64 digits each. With one five-gate full adder per column, how many gates does a 64-bit ripple-carry adder need?
- 64
- 320
- 4,096
Show answer
B. 320
320: 64 columns times 5 gates. Real chips usually spend extra gates on faster designs, because waiting for a carry to ripple through 64 columns would slow down every addition.
Stibitz's switches were relays, flipped by an electromagnet. The switches in your phone have no moving parts at all. So what flips them?
What flips the switches
The switches in a chip are transistors: switches turned on and off by a voltage instead of a finger or a magnet. The output of one gate is a voltage, and that voltage flips the transistors inside the next gate. That is why gates can be chained, one after another, into an adder.
The whole full adder fits in two lines of math. Here \(\oplus\) means XOR, a dot means AND, and a plus sign means OR:
Check the full adder in every case (try one row yourself first)
- List every case. Three inputs, each 0 or 1, make 2 × 2 × 2 = 8 cases:
\[ \begin{array}{ccc|c|cc} A & B & C_{in} & \text{total} & C_{out} & S \\ \hline 0&0&0&0&0&0 \\ 0&0&1&1&0&1 \\ 0&1&0&1&0&1 \\ 0&1&1&2&1&0 \\ 1&0&0&1&0&1 \\ 1&0&1&2&1&0 \\ 1&1&0&2&1&0 \\ 1&1&1&3&1&1 \end{array} \]2. The sum digit. A chain of XOR gates outputs 1 when an odd number of its inputs are 1. The odd totals are 1 and 3, and those are exactly the rows where the right digit of the total in binary is 1.
- The carry. The total is 2 or 3 exactly when at least two inputs are on. That happens in one of two ways: A and B are both on (the first AND gate), or exactly one of A and B is on and the carry in is on (the second AND gate, fed by \(A \oplus B\)). The OR gate lights when either way happens.
- Put the two digits together. In all 8 rows,
\[ 2\,C_{out} + S = A + B + C_{in} \]so the two lamps always spell the total in binary.
- One gate builds them all. A NAND gate (an AND gate with its output flipped) can be wired into NOT, AND, OR and XOR. An XOR takes four NAND gates. So, in principle, a whole computer can be built from NAND gates alone.
Where it shows up
- Every processor has an arithmetic logic unit (ALU): adders plus gates for AND, OR and comparing numbers. Subtraction and comparison usually reuse the same adder.
- Stairway lights with two switches work like an XOR gate. Depending on the wiring, "on" can mean the two switches match instead of differ.
- Encryption and error checks use XOR: XOR a message with a secret key to scramble the message, and XOR the scrambled message with the same key to get the original back.
- Overflow bugs hit counters, scores and clocks that run out of digits, the same way 15 + 1 rolled over to 0 on four switches.
Crash Course Computer Science builds the same adder, and then a whole ALU, in an 11-minute animated episode. The video can't let you flip the switches, so test each step in the widgets above.
Where to go next
You can now explain how a chip adds: switches make gates, five gates make a full adder, and a chain of full adders adds whole numbers. Each piece opens a bigger question:
- How does a chip remember a number after the switches that set the number turn off?
- How does a computer subtract when all it has is an adder?
- If every carry has to ripple through every column, how do fast chips avoid the wait?
- How does a line of code like
total = a + bend up flipping these switches? - What is the "3 GHz" on a laptop actually counting?
Ask Phy
- Show me how two gates wired in a loop can remember one bit.
- Walk me through 9 − 5 on a 4-bit adder using two's complement.
- Why is a carry-lookahead adder faster than a ripple-carry adder? Use a 4-bit example.