"What does it mean?" and addition examples

With a knowledge of carry bits and single-bit adders, we are ready to dive into some examples of binary addition. Sounds pretty fun, right? Well, I know it does, but before we get into that I want to comment on why we're spending so much time talking about things that might not seem very important.

You came here wanting to learn about computer science and how a computer does what it does, right? Well, believe it or not, the addition of two numbers is a very, very important part of computers. In fact, there are only two more big things you need other than addition in order to have a fully functioning computer. If you create a computer that can add two numbers together (including negative numbers, which we'll get to another time), can "branch" and "jump" (basically, this means handling if-then statements and loops), and has a memory system (meaning there are places you can store data and retrieve it later), then you can program that computer to do anything you can think of. You can program video games, word processors, web browsers or anything else. It's kind of crazy that such complex programs have been created out of such simple building blocks.

Of those extremely basic building blocks of computing, I decided that talking about adders and the binary number system was the easiest and best place to start. A working knowledge of adders and binary will make learning the other concepts far easier. This is all in stark contrast to how computer science is most often taught in the world. It is far more common to start teaching computers with high-level computer languages that hide all of the important details about how computers work. You should consider yourself lucky that I trust you enough to start with the important stuff, saving the boring high-level stuff for later.

Speaking of important stuff, let's get back to examples of 8-bit binary addition. Let's first look at an example where none of the single-bit adders do any carry-out or carry-in (sorry for the poorly formatted text in these examples, I'll figure it out eventually):

+0b1100 1100 (204 in decimal, that extra + at the beginning is just to get the text to line up)

+0b0011 0011 (51)

=

+0b1111 1111 (255)

For each bit of the answer we are adding only 0b0+ob1, giving us 0b1 for the result bit. Now for an example that uses carry:

+0b0000 0111 (7)

+0b0000 0011 (3)

=

+0b0000 1010 (10)

We had to use carry for the "ones place," "twos place," and "fours place." The addition for the "eights place" consisted of 0b0+0b0+0b1 (that last 0b1 being the carry-in from the addition of the "fours place"). Let's look at one more extreme case of carry in action:

+0b1111 1111 (255)

+0b0000 0001 (1)

=

+0b0000 0000 (???)

This makes it look like adding 1 to the maximum value of a byte (255), will result in 0 as the answer. What's really going on is that the true answer (256) cannot be represented by only 8 bits. It is impossible. The true answer consists of 8 bits of 0, and the final carry-out bit set to one. When addition results in carry-out beyond the limits of what the answer can store, we call this "overflow."

This means that the answer that's in the remaining 8 bits is not the right answer, and that you messed up by trying to add two numbers that were too big for the number of bits you wanted the answer to fit in. The best thing to do in this case is to add two 16-bit numbers together, because then you will have the ability to represent the number 256 without any problems. You can convert an 8-bit number to a 16-bit number by just adding extra 0s to the front of it. This is what that addition then looks like (again, sorry for the horrible formatting):

+0b0000 0000 1111 1111 (255)

+0b0000 0000 0000 0001 (1)

=

+0b0000 0001 0000 0000 (256)

In this day and age when we have 64-bit adders at our disposal it is very rare to add numbers together that are too big to fit into the result bits and cause overflow, unless you're doing something weird or wrong (or you're a scientist). Next time we'll take a break from adding binary numbers, and talk about computer memory. However, we're not totally done with addition yet, as we still need to cover subtraction, which is a just special form of addition with negative numbers.

Carry out, carry in

We've covered addition for two single bit binary values, and how the outcome of that addition is stored in the result bit and the carry-out bit. In a real computer's binary adder, the addition of two (and only two) values only happens for the least significant bit of the binary number (or the "ones place"). For the rest of the bits, we have to add three different values together: the two bits being added like before, plus the carry-in bit, which is just the carry-out bit from performing addition on the bits we just added together (moving right-to-left, like the decimal addition we're used to).

The carry-out of addition is handed to the carry-in of the adder for the next higher bits, so that they can use it to perform their addition. The "ones place" carry-out becomes the carry-in for the "twos place," and the carry-out of the "twos place" becomes the carry-in for the "fours place," and so forth (remember, this is binary, so our places are: 1s, 2s, 4s, 8s, 16s, etc.). The "ones place" is the only place that doesn't use any carry-in at all, because there is nothing lower than the "ones place" that the carry-in could have come from.

When we consider the carry-in bit there are suddenly twice as many options for combinations of inputs to our single-bit adder. Here are all of the combinations:

0b0+0b0+0b0: result=0b0, carry-out=0b0

0b0+0b0+0b1: result=0b1, carry-out=0b0

0b0+0b1+0b0: result=0b1, carry-out=0b0

0b0+0b1+0b1: result=0b0, carry-out=0b1

0b1+0b0+0b0: result=0b1, carry-out=0b0

0b1+0b0+0b1: result=0b0, carry-out=0b1

0b1+0b1+0b0: result=0b0, carry-out=0b1

0b1+0b1+0b1: result=0b1, carry-out=0b1

Even though there are twice as many inputs, there is only one single more output (result=0b1, carry-out=0b1). This is the one combination that cannot be seen from adding together two (and only two) single-digit binary numbers. Notice also that whenever at least two inputs are 0b1, then the carry-out will be 0b1 regardless of what the third input is. Also notice that the result bit is 0b1 only if there is an odd number of 0b1 values among the inputs. Interesting.

Multi-bit adders are created by stringing together many single-bit adders, feeding the carry-out of one directly into the carry-in of the other. When adding two binary numbers together, one number plugs in each of its bits into one input of each single-bit adder, and the other number plugs its bits into the other input of each single-bit adder. After the electrical circuit that comprises the adder has a chance to stabilize, the answer of the addition will appear in the result bits of single-bit adders, plus one final carry-out at the far end. You can make an 8-bit adder by stringing together 8 single-bit adders in this way, and the result will be 8-bits long, plus the carry-out (so really 9-bits long).

Next time we'll show examples of multi-bit binary addition in action, and I might even explain sometime soon what all this has to do with computer science.

Adding single bits

Today we'll look at what it's like to add two single-digit binary numbers together. Each of the two single-digit binary numbers can either have the value 0b0 or 0b1. Considering both bits together, this means there are 4 different possible combinations of input for single-bit addition ((0b0+0b0), (0b0+0b1), (0b1+0b0), and (0b1+0b1)). Here are the results for all of those additions:

0b0+0b0 = 0b0 = 0

0b0+0b1 = 0b1 = 1

0b1+0b0 = 0b1 = 1

0b1+0b1 = 0b10 = 2

The result for each of those additions can be represented by a single result bit EXCEPT 0b1+0b1, which results in the 2-bit number, 0b10 (the decimal number 2). This leads to a very important observation. When adding two binary numbers, it is possible that the resulting number will require 1 more bit to store the result than either of the inputs. Possible, but not guaranteed to need it. It's exactly the same as in the decimal number system. Adding two single-digit decimal numbers might result in a single-digit answer, as in the case of 2+2=4, or it might result in a two-digit answer, as in the case of 7+8=15. You can never require 3 result digits when adding two single-digit numbers, as 9+9=18 (the result of 9+9 is the largest possible number you can get from adding two single-digit values).

So we know that the addition of two single-digit binary numbers may or may not produce a two-bit result, but what if it does? What does a real computer do with that? In a real computer binary adder, the second bit of the answer is called the carry-out bit. The first bit is called the result bit. When learning arithmetic in elementary school, we are taught about the carry-out bit, or rather the carry digit. When you are adding two numbers you might get "8+6=four carry the one, for a total of fourteen." It's the exact same thing with single-bit binary addition. Let's look again at previous additions in the context of result bits and carry bits.

0b0+0b0, result bit = 0, carry-out bit = 0

0b0+0b1, result bit = 1, carry-out bit = 0

0b1+0b0, result bit = 1, carry-out bit = 0

0b1+0b1, result bit = 0, carry-out bit = 1

So if there's a carry-out bit, does that mean there's a carry-in bit? There is, actually, and it is instrumental to multi-bit addition, which we'll talk about next time.