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.