From Switches to Addition

Here is a surprising fact: a computer doesn't really "understand" anything. It doesn't know what a number is, or a letter, or a picture. All it can do is move electricity around through switches that are either on or off. Everything else, from spreadsheets and video games to the web browser you're using now, is built on top of that one humble ability.

So that's where we begin. Every diagram in this chapter is live: click on things.

A switch and a lamp

Picture the simplest electrical circuit there is: a battery, a lamp, and a wire that runs from one side of the battery, through the lamp, and back to the other side. A battery pushes electric current around a loop. If the loop is complete, current flows and the lamp lights up.

Now cut the wire and put a switch in the gap. A switch is just a little bridge you can raise or lower. When it's closed the bridge is down, the loop is complete and the lamp is on. When it's open the loop is broken and the lamp is off.

This is the first big idea in the book, and it's worth stating plainly: a switch has exactly two states. On or off. Closed or open. Current or no current. There's no "half on". We'll give these two states the names 1 and 0.

Two switches make a decision

One switch is not very interesting. Things get better with two. There are two natural ways to wire them.

In a row (engineers say in series): the current has to cross S1 and then S2 to reach the lamp. If either one is open, the path is broken.

Side by side (in parallel): now the current has two possible paths. It can go through S1 or through S2. Only one of them needs to be closed.

Look at what just happened. With nothing but wire and switches we built two tiny decision-makers: one that answers "are both of these true?" and one that answers "is at least one of these true?". We'll call them AND and OR.

Switches that flip switches

There's a problem with our switches: you have to flip them with your finger. A computer needs to make millions of decisions a second, with the result of one decision feeding into the next. What we need is a switch that's flipped by electricity instead of by a finger. Then the output of one circuit can control the switches in another circuit, and so on, endlessly.

Engineers have built this kind of switch three times over, each version smaller and faster than the last:

• Relays (1930s–40s): an electromagnet physically pulls a metal contact closed. They're clicky, slow and the size of a thumb.
• Vacuum tubes (1940s–50s): glowing glass bulbs with no moving parts, but hot and fragile. ENIAC, finished in 1945, used about 17,000 of them.
• Transistors (invented at Bell Labs in 1947): a sliver of specially treated silicon that conducts or blocks current depending on the voltage at its control terminal (called the gate). Today's transistors are only a few dozen atoms across and can switch billions of times per second.

For everything in this book, you can think of a transistor exactly like the demo above: a switch whose handle is a wire.

Counting with only two digits

If our switches only know 0 and 1, how can a computer work with a number like 42? The same way you write numbers bigger than 9 using only the digits 0 to 9: place value.

In ordinary decimal, each place is worth ten times the place to its right: ones, tens, hundreds, thousands. In binary, each place is worth two times the place to its right: ones, twos, fours, eights, sixteens, and so on. Each place holds a single 0 or 1, called a bit (short for binary digit). To find the value of a binary number, add up the places that hold a 1.

A group of 8 bits is called a byte, and it can hold any number from 0 (all off) to 255 (all on). Try pressing + 1 when all eight bits are on: the number wraps back around to 0, like a car's odometer rolling over. Remember this; it's going to matter.

The important part: a number is now just a row of switches. Anything we can do to switches, we can do to numbers.

Logic gates

Wiring transistors together one at a time would get tedious fast. So engineers package a few transistors into standard building blocks called logic gates. A gate takes one or two input bits and produces one output bit according to a fixed rule. Each gate has its own symbol, which you'll see in circuit diagrams everywhere.

A gate's rule is fully described by its truth table: a list of every possible input and the output it gives. Since each input can only be 0 or 1, a two-input gate has just four rows. (You can click a row of the table to jump to it.)

NOT: the contrarian

The simplest gate has one input and outputs the opposite.

AND: both, please

Exactly our two switches in series: the output is 1 only if A and B are both 1.

OR: either will do

Our two switches in parallel: the output is 1 if A or B (or both) is 1.

XOR: one or the other, but not both

The exclusive OR outputs 1 when its inputs are different. It looks like OR with an extra curve at the back. Keep an eye on this one; it's about to become the star of the show.

Adding in binary, by hand

Now we have everything we need to make a circuit do arithmetic. First let's see how addition works in binary with pencil and paper. It's the same column-by-column method you learned in school, with a much smaller table to memorize:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10   ← that's "two" in binary: write 0, carry 1
1 + 1 + 1 = 11   ← "three": write 1, carry 1

Here's 5 + 3, worked out the long way. Start at the right-hand column and carry into the next column whenever a column adds up to two or more:

 carry   1 1 1
         0 1 0 1      5
       + 0 0 1 1    + 3
       ---------    ---
         1 0 0 0      8

Now look closely at the rules for adding one column of two bits, and compare them with the truth tables from earlier:

• The sum digit is 1 when exactly one of the bits is 1. That's XOR!
• The carry is 1 only when both bits are 1. That's AND!

That's the "aha" moment of this chapter. Addition, the thing we think of as math, turns out to be logic in disguise.

The half adder

So let's build it. Send the two bits A and B into an XOR gate to get the sum, and into an AND gate to get the carry. The dot where a wire splits is called a junction: the same signal goes both ways.

Just two gates, and we can add two bits. It's called a half adder because it's missing something. Look back at the pencil-and-paper example: in every column except the rightmost, we're adding three bits. There's A, there's B, and there's the carry coming in from the column to the right.

The full adder

To add three bits we chain two half adders. The first adds A and B. The second adds that result to the incoming carry (Cin). If either half adder produced a carry, the column carries out, so an OR gate combines them into Carry out.

Notice something about that diagram. We didn't draw the XOR and AND gates inside the half adders. We drew each one as a box with labelled inputs and outputs, because we already know what's inside and no longer need to look.

This trick is called abstraction, and it's the single most important idea in all of computing. Hide the details inside a box, give the box a name, and use it as a part in something bigger. It's the only reason humans can design a chip with billions of transistors: nobody thinks about all of them at once. We'll do this at every level of the book.

Chaining them: a 4-bit adder

Now the payoff. Put one full adder (FA) in each column, and connect each column's carry out to the carry in of the column to its left, exactly as you carry with a pencil. The rightmost column has no carry coming in, so we tie its input to 0.

Watch carefully with slow motion on. Try 15 + 1: for a moment the sum lamps show wrong answers, while the carry is still making its way down the line. Each full adder has to wait for the one to its right before it can be sure of its own answer. This design is called a ripple-carry adder for exactly that reason. In a real chip each step takes a tiny fraction of a nanosecond, but it adds up. We'll come back to this.

Now try 7 + 9. The answer is 16, but four bits can only hold 0 to 15. The four sum lamps show 0000 and the extra 1 spills out of the left end as the final carry out. This is called overflow, and it's the same "odometer rollover" you saw with the byte counter.

Meanwhile, inside a real CPU

What you just built is, quite literally, a small slice of the processor in your computer. When a program adds two numbers, the CPU runs an add instruction, and that instruction sends two numbers through an adder made of full adders. It's just much wider: a modern 64-bit processor adds numbers 64 bits at a time.

Here's 5 + 3 written in x86-64 assembly language, the instruction set used by most desktop and laptop PCs. rax and rbx are registers: small, fast storage slots inside the CPU, each holding one 64-bit number.

mov  rax, 5        ; put 5 in register rax
mov  rbx, 3        ; put 3 in register rbx
add  rax, rbx      ; rax = rax + rbx  → 8

And the same thing in RISC-V, a newer, cleaner design that's popular in teaching and in many small chips. Its registers have names like a0 and a1:

li   a0, 5         # load 5 into register a0
li   a1, 3         # load 3 into register a1
add  a0, a0, a1    # a0 = a0 + a1  → 8

Same idea, different spelling. The interesting difference is what each one does with the carry out, the lamp on the far left of your adder:

• x86-64 saves it in a special one-bit register called the carry flag (CF). There's even an instruction, adc ("add with carry"), that feeds the carry flag into the next addition, just like wiring one adder's carry out to the next one's carry in. That's how a 64-bit CPU can add 128-bit numbers.
• RISC-V has no flags at all, a deliberate choice that keeps the chip simpler. If a program needs the carry, it works it out with one more instruction: if the sum came out smaller than one of the inputs, the addition must have overflowed (sltu, "set if less than, unsigned").

One last thing: real CPUs don't use the ripple-carry design for 64 bits, because the carry would have to ripple through 64 stages. Instead they use cleverer circuits, such as carry-lookahead adders, that figure out all the carries at once with extra gates. They spend more transistors to save time, a trade-off you'll see again and again in this book.

Try it yourself

1. In the gate demos, which gate's output is 1 in exactly one row of its truth table?
   Show answer

   AND. Its output is 1 only when A = 1 and B = 1. (OR is 1 in three rows, XOR in two.)
2. Using the 8-bit counter, what is binary 1111 1111 in decimal? What about 1000 0000?
   Show answer

   255 (128+64+32+16+8+4+2+1) and 128. Notice that a 1 followed by all zeros is always a power of two, just like 1000 is a power of ten.
3. In the 4-bit adder, turn slow motion on and load 15 + 1. How many steps does the carry take to settle? How many would a 64-bit ripple-carry adder need in the worst case?
   Show answer

   4 steps: one per full adder, because each one waits for the carry from its right-hand neighbour. A 64-bit ripple adder could need 64 steps, which is why real CPUs use carry-lookahead designs.
4. Load 7 + 9 into the 4-bit adder. Why do the sum lamps show 0?
   Show answer

   7 + 9 = 16 = binary 1 0000. That needs five bits. The four sum bits are all 0, and the fifth bit comes out as the carry out. On x86-64, the carry flag would be set to 1.

What we learned

• A switch has two states, which we call 1 and 0.
• Switches in series make AND; switches in parallel make OR.
• A transistor is a switch controlled by electricity, so circuits can control other circuits.
• Numbers can be written in binary as rows of bits, each place worth twice the one to its right.
• Logic gates (NOT, AND, OR, XOR…) are small groups of transistors with simple rules.
• Binary addition is logic: sum = XOR, carry = AND. A half adder adds two bits; a full adder adds three.
• Chaining full adders gives a ripple-carry adder, the heart of every CPU's add instruction.
• Abstraction, hiding details inside a box, is how we'll climb all the way up.

Our adder has a gap, though. It can only add positive numbers. In the next chapter we'll learn how computers represent negative numbers, and discover that the very same adder can also subtract, with just a few extra gates. We'll also meet hexadecimal, the shorthand programmers use to write long binary numbers.