[NOTE: This is an entry in the 3Blue1Brown Summer of Math Exposition for 2021. Full disclosure: Originally, I wrote the multiplier and divider visuals without the detailed explanation as a project for a class this spring. Over the summer I've been extending it to the broader 3-part explanation that does addition and subtraction as well. I was already somewhat into the design when I heard about SoME, but apart from the original form, this has not been published previously.]
You're probably aware that computers store numbers as a series of 0's and 1's. Using just 0's and 1's is called "binary", and the binary digits are called bits. These bits, the 0s and 1s, are sent around in various complicated circuits to do calculations.
But how does the computer actually do arithmetic? Before we can get into that, we need to learn how the computer actually stores numbers in the first place. There are a few different methods, but we'll focus on whole numbers for now.
Humans generally use base ten notation, which means that a number like 314 means three hundreds, one ten, and four units. Computer wiring generally uses base two, or binary, where the only digits are 0 and 1 and the digits use powers of two (1, 2, 4, 8, 16, 32, ...). For example, 110 in binary means not "one hundred and ten" but "one four and one two", or 6. To help avoid confusion, I'll use this font and color for binary numbers with multiple digits: 10 means two; "10" in normal font means ten, the number after nine.
I promised this would be interactive. Here's a simple exploration to show how binary numbers work. I've included six bits, which means the maximum number you can reach is 26 - 1, or 63. (With six decimal digits you could reach 106 - 1 = 999,999.)
This one just shows you the value of a 6-bit number. You can click on the bits to change them.
Now, in order to do anything useful with these numbers, we need to have ways do to computations on bits. As is common in computer design, we start with the most basic possible components, and work our way up.
What are the simplest possible operations? Well, taking the opposite of a bit (change 0 to 1 and vice versa) is useful. That's called a "NOT gate", because it takes in a value and outputs whatever that value is not.
But to do real computations, we need bits to interact with each other. The next simplest kind of operation involves two inputs. There are many possibilities, but the simplest ones that come to mind are the following:
The English word "or" is annoyingly ambiguous; sometimes it allows both ("you must be 48 inches tall or accompanied by an adult"; they wouldn't turn away two tall adults who want to ride together!) and other times it does not ("it comes with salad or fries" probably means you pick one). Computer scientists cannot tolerate this kind of ambiguity, and so they have decided to call the "one or both" option "OR". When you want "one or the other, but not both", they call it "exclusive or", also known as "XOR".
Why am I saying this? Well, first, I want to make it clear what an "OR" gate does when you see it in a circuit. Second, the XOR gate, though more complicated, is surprisingly useful later on...
| First Input | Second Input | AND | OR | XOR |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
The above is a "truth table" for three of the four main operations. (The fourth, NOT, only has one input.)
Now, I will not go into how one actually builds a NOT gate or an AND gate. That's getting a bit too far into electrical engineering. Instead, we'll treat those as "atoms", basic components from which everything else will be built.
Instead, here is another exploration. There are no numbers this time. The squares are the outputs; you can't change them directly. In case you skipped the instructions above: Green is 1, red is 0. Click on circles to switch them. Squares are the output. The shapes I've used are common in electrical engineering, but I've also added the symbols &, O, and X to make it more clear. (If you're still confused as to which gate is which—and I admit to being a little unclear on that—the best way to learn is to try it yourself!)
With these four gates, we can make almost anything. Probably the easiest thing to start with is arithmetic, because numbers are so fundamental to computations. Of the four basic operations, addition is clearly the easiest of them, so let's start there.
In fact, let's start with the simplest case of the simplest case: adding two individual bits. (In other words, we're adding two numbers that can be either 0 or 1.) Now, the result could be either 0, 1, or 2, which is three possiblilities, so we'll need more than one bit for the output. For these purposes, we'll have two output bits, one that means "1" and one that means "2".
Here's what we're going for. On the left, I've made a simple adder to show what we're doing. On the right, I have a set of adjustable logic gates. You can click or tap the arrows to change the gates.
See if you can get the rightmost output square to turn on when A + B = 1, and the leftmost one to turn on when A + B = 2. If you think you have it, click the "TEST" button to see if you're right! (Note that you have to make it work for EVERY possible input. I'd highly recommend thinking about the different gates, rather than just trying all 9 possible gate configurations.)
Did you figure it out? If you did, good job! If not, let's see how we can discover it from scratch.
With these kinds of problems, it helps to write down exactly what we want the wiring to do. We have two inputs, A and B.
It should be fairly obvious by now that "2" needs to be an AND gate. I hope you've also spotted that "1" should be an XOR gate, but if you guessed inclusive OR, it's okay -- mistakes are part of learning! (That also shows the value of writing everything out. It's much harder to forget about the double-1 case if you have to write it out. In fact, we also could have made a truth table; comparing it to the one for AND/OR/XOR would reveal the answer immediately.)
What we just conceptualized was called a "half adder". Why half? Because if you're trying to add two numbers, sooner or later you have to worry about carrying. The "2" output from above would be our carry; it's a little like the tens digit in an addition like this:
addition: (1) 58 + 66 ---- 4 (8 + 6 = 14, carry the 1) 124
The lonely "4" above the answer represents the fact that you normally write the 4 first, then carry the 1, and add 1 + 5 + 6 = 12.
So how can we handle carries? This is a bit complicated, so we'll definitely need a truth table. See if you can do it yourself!
We'll technically have three inputs here, but one of them is the "carry" bit that represents the "2" output of the previous column. Also, there could be three ON (1) inputs. Instead of making a third output, we can just say that if all three are on, we'll turn the "1" and "2" inputs on. (Just like binary! 1 + 2 = 3.)
| Input A | Input B | Carry In | Output 1 | Output 2 |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 1 | 0 | 0 | ||
| 0 | 1 | 0 | ||
| 1 | 1 | 0 | ||
| 0 | 0 | 1 | ||
| 1 | 0 | 1 | ||
| 0 | 1 | 1 | ||
| 1 | 1 | 1 |
Did you get it? Scroll down for the answer. The right column has value 2 but I wrote 0s and 1s because that is more standard (there's no second voltage level or anything like that).
| Input A | Input B | Carry In | Output 1 | Output 2 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
But how do we wire this? Well, we're trying to add A + B + C. We can think about splitting that up into (A + B) + C, that is, doing the first addition at the beginning and adding extra stuff on for the carry bit.
I'll have you see if you can do it. I'll give you a hint by providing the general layout of the circuit as well as two of the five gates. See if you can fill in the rest!
So once we have a full adder, all we need to do for multiple bits is to chain a whole bunch of them together!
On the left side, I've put a basic implementation of the hardware showing the individual gates that make a basic four-bit adder. On the right, I've abstracted that away to a single component that does the same thing.
Click on red and green circles to change the input bits. Red = 0, green = 1. The square bits are the outputs. The numbers show what your inputs and outputs are in decimal, but you cannot type numbers in. I did that on purpose. Click on the bits directly!
(There are no adjustable gates this time. You can still click the bits, but the circuit is correct and complete.)
Well... if you've gotten this far, take a moment to feel good about yourself. You're learning!
All right... Well, we've just done addition. The next simplest operation is subtraction. When you're ready, let's move on to part 2!