How Do Computers Add? Part 2
Have you ever wondered how computers and calculators—both of which are nothing more than mindless boxes of plastic, wires, and other strange parts—manage to add numbers? And so quickly! Math Dude has the second part of the story.
Jason Marshall, PhD
Listen
How Do Computers Add? Part 2
After weeks of learning about binary numbers, Boolean algebra, and the math that makes the tiny electronic components known as logic gates tick, we’re finally ready to begin tackling the big questions we’ve been working towards: How do computers and calculators add? And how do they do it so quickly? I’m happy to say that those are exactly the questions we’ll be answering today..
Review: Logic Gates
As we talked about last time, the key to building machines that can add are something called logic gates. These tiny electronic components perform Boolean operations on one or more input bits and spit out a binary output bit as the result. So far we’ve learned about three fundamental logic gates that implement the AND, OR, and NOT operations of Boolean algebra. But are there others? In particular, are there any other logic gates that are useful for building machines that can add?
Exclusive OR (aka, XOR)
Indeed, there are several other logic gates that are built by combining two or more primitive AND, OR, and NOT gates. Of particular importance for today is a gate called “exclusive OR”—aka, XOR. An XOR gate does exactly what it sounds like. By which I mean that while a regular OR gate gives TRUE when either or both inputs are TRUE, an exclusive OR gate gives TRUE exclusively when one or the other—but not both—inputs are TRUE. In the world of 1s (meaning TRUE) and 0s (meaning FALSE), this means that 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, and (this is the biggie) 1 XOR 1 = 0.
Why is this XOR logic gate useful? To understand that we need to think back to how binary addition works. In particular, let’s think about all the things that can happen when we add two bits—namely, we can have: 0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1, or 1 + 1 = 10. If you compare the first three results with the first three XOR operations we talked about earlier, you’ll see that they are identical.
And what about the last XOR operation—1 XOR 1 = 0? How does it compare to the last binary addition problem, 1 + 1 = 10? It turns out that the 0 from the XOR is what’s called the “sum bit” (which is just the digit on the right) of the binary addition problem. The 1 from the 10 in 1 + 1 = 10 is what’s called the “carry bit” (exactly analogous to the carry digit in normal decimal addition). The big take-away from this is that the XOR operation gives us the sum bit in binary addition. Which means that we’ve found the first half of the solution we’ve been working towards! And it also means that an XOR logic gate is the first big piece of our adding machine.
How to Build an XOR Gate
Before we figure out how to build the rest of our adding machine, let’s take a quick look at how you can actually build an XOR gate. There are lots of ways to do it, but one way is to use one OR, two AND, and one NOT gate. Both input bits are fed into the OR gate on one branch (which we’ll call the top branch) and an AND gate on the other. The output of the AND gate on the bottom branch passes through a NOT gate, and is then combined with the output of the top branch’s OR gate in the final AND gate…like this:
If you plug the possible values of the two input bits in and trace out the results as you go through each AND, OR, and NOT gate, you’ll find that the output bits are exactly what you’d expect from an XOR gate. For example, if the first input bit is 1 and the second is 0, the OR in the top branch outputs 1 (since 1 OR 0 = 1) while the AND on the bottom branch outputs 0 (since 1 AND 0 = 0). The 0 from the AND on the bottom then passes through a NOT gate, which means that it outputs 1. The 1s from the top and bottom branches then enter the last AND gate which outputs 1…as expected. On the other hand, if both input bits are 1, the OR in the top branch outputs 1, while the AND followed by the NOT gate in the bottom branch outputs 0. Which means that the final AND gate outputs 0 (since 1 AND 0 = 0).
As you can check, this arrangement of gates works for each of the other two input bit combinations as well. Pretty cool, right?
The Rest of the Story…
Now that we know how XOR works (and even how to build an XOR gate), we’re well on our way towards understanding how computers and calculators add. In particular, since we know that computers work in binary, we know that they must first convert the decimal numbers we give them into their binary number equivalents. And we now know that half of the problem of adding these binary numbers up—the part that involves finding the so-called sum bit—is solved using an XOR gate.
But how do we solve the other half of the problem—the problem of finding the carry bit? And how do we then extend our adding machine so it can add bigger numbers? As we’ll see next time, we just need to make a few (relatively simple) additions to the machine we’re building. After that, you’ll finally know everything you ever wanted to know about how computers and calculators add!
Wrap Up
Okay, that’s all the math we have time for today. Remember to become a fan of the Math Dude on Facebook where you’ll find lots of great math posted throughout the week. If you’re on Twitter, please follow me there, too. Finally, please send your math questions my way via Facebook, Twitter, or email at mathdude@quickanddirtytips.comcreate new email.
Until next time, this is Jason Marshall with The Math Dude’s Quick and Dirty Tips to Make Math Easier. Thanks for reading, math fans!
About the Author
Jason Marshall is the author of The Math Dude’s Quick and Dirty Guide to Algebra. He provides clear explanations of math terms and principles, and his simple tricks for solving basic algebra problems will have even the most math-phobic person looking forward to working out whatever math problem comes their way.