Summing bits
When I first discovered assembly language, it felt like the computer was exposed to me at its most fundamental level and now I could understand how it really works. All those elaborate structures of a high-level programming languages distilled into the most basic instructions. But then I thought: “Hold on, how does the computer execute that instruction?” I had to go deeper, and that’s where logic gates come in.
A basic logic gate
A logic gate is an electronics component. Let me show you an example. You can click on the switches on the left and see what that does to the output on the right.
A couple of notes, in case you’re new to logic gates.
- A logic gate takes input and produces output.
- The input consists of 0s and 1s, and the output consists of 0s and 1s.
- This particular logic gate is called an or-gate, because it produces a 1 if A = 1 or if B = 1.
- We usually talk about 0s and 1s when dealing with logic gates, but in reality, it’s all about electricity. If the voltage is low, we call that a 0; if the voltage is high, we call that a 1. You don’t need to worry about that when looking at logic gates, though.
There are only a handful of basic logic gates and they are all very simple to understand. The cool thing is: that’s all you need to build a processor. Going from machine code to logic gates is like moving from a high-level programming language to assembly language: the building blocks become much simpler; the complexity is in putting them together to do something useful.
To drive my point home, I’ll build a digital circuit that can sum two binary numbers. This will require only three different types of logic gate. Putting it all together will require some mental gymnastics, but nothing too daring. It’s like doing an intricate puzzle, and puzzles are fun!
Summing two bits
Let’s tackle this one step at a time and start with summing two lone bits. Here are all the possibilities.
| Calculation | Binary result | Decimal result |
|---|---|---|
| 0 + 0 | 00 | 0 |
| 0 + 1 | 01 | 1 |
| 1 + 0 | 01 | 1 |
| 1 + 1 | 10 | 2 |
As you can see, the result has two bits, but since I’m taking this one step at a time, I’m only going to worry about the rightmost bit for now. So, I want a logic gate that produces a 1 if the first input bit is 1 or the second input bit is 1. That sounds a lot like the gate we’ve already seen! Alas, it isn’t. If you play around with it, you’ll see that the or-gate produces a 1 even if both input bits are 0, and that’s not what I need here. The logic gate I do need, is an xor-gate.
Nice. That brings me halfway through summing two bits. The name xor is short for exclusive or, by the way.
Carry the 1
Now I want to deal with the leftmost bit of the result. As with decimal arithmetic, that one is called the carry. As the table above shows, the carry is 1 when the first input bit is 1 and the second input bit is 1. Does there, perhaps, exist an and-gate? There sure does.
How convenient.
Half adder
To finish my one-bit adder, I just have to put the two gates together, like so.
This is called a half adder. The name may make you suspect that there’s also such a thing as a full adder. There is and we need it.
Full adder
If I want to add two 2-bit numbers, I run into a small problem: if summing the first two bits produces a carry, I need to add that carry to the second two bits. That means that I need to be able to sum three 1-bit numbers. In other words, in order to calculate 01 + 11, I have to be able to calculate 1 + 1 + 1. This is where the combination of logic gates becomes a little harder to understand, so you may want to take some time to study this one.
This is called a full adder. It sums two bits and a carry. I now have what I need to build a machine that can sum binary numbers.
A multibit adder
Since I want to sum 2-bit numbers, I need two adders, one after the other. The first sum never needs to deal with a carry, so a half adder suffices for the first step. Again, this one requires a little study, but you should be able to recognize the half adder and the full adder in there, and you already know how those work.
If I want to sum 3-bit numbers, I just add another full adder. Summing 4-bit numbers? Just use four adders. Guess how many the 8-bit machine will have.
Just imagine being able to explore the logic gates of an entire processor this way. That’s what I’m building! The 8-bit machine will show you how code works at the machine code level and at the logic gates level. That’s exciting! Isn’t that exciting? I think that’s exciting.