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.