Two's compliment

Two thinks you look very nice today. Oh wait, it's not supposed to say "compliment." I meant to say "two's complement" (with an 'e' in the middle of that second word), as in "those shoes would complement two's outfit very well." That time I used the right word at least, but we're still not supposed to be talking about fashion.

What's really going on is that I'm finally going to talk about negative binary numbers. I kept putting this off because I think it's confusing, and I don't want anyone who reads this to feel confused (other than the confusion I intentionally created with the first paragraph). There are two things about two's complement numbers that are difficult for people (including me) to remember and understand. The first is how to convert a positive binary number into its negative, two's complement form. The second is why we would even want to do that, and what benefit comes from going to the trouble.

It's simple to represent a negative number. Just take the original number and put a '-' in front of it. Unfortunately, with binary numbers in computers we don't have minus symbols. All we have are 0s and 1s. So that means that using only 0s and 1s we somehow have to differentiate between positive and negative numbers. In the two's complement form we do this by kind of pretending that the "most significant bit" is the positive/negative symbol (if it's 0 it's a positive number, and if it's 1 it's a negative number). We call this the "sign bit."

I have to clear up something from that last sentence. The "most significant bit" is the left-most bit when writing out the binary number, and its value has the biggest effect on the final value of the entire binary number. For example, in an 8-bit number, the "128s place" bit is the most significant bit. The 1 in 0b100 0000 is the most significant bit.

So now we know to look at the most significant bit to see if we're dealing with a positive or negative number, but the trick with two's complement is what's going on with all the rest of the bits. It's not enough to put a 1 for the sign bit and then read the rest of the bits the same as we always did. Two problems with that. First, it would be too easy. Second, it makes addition and subtraction of negative numbers more complicated than I'll show it is in a minute.

With two's complement you have to do the following to turn a positive number into its negative (I've put this off until the last possible moment): First, invert all the bits (turn all the 0s to 1s and vice versa). Second, add 1 to it. I know. It doesn't make sense. It sounds stupid. Sure, maybe the first part, flipping all the bits, can be justified because negative numbers live in Bizzaro World, so maybe everything's just opposite of a positive number. But why add 1 after that? I don't have a good explanation of that, other than that the resulting representation of the negative binary number is very convenient.

Let's do a couple of examples using 8-bit binary numbers to clear our brains.

0b0000 0001 (decimal 1)
invert all the bits
0b1111 1110
and add 1
0b1111 1111
So the two's complement representation of -1 is 0b1111 1111. Note that the most significant bit, or sign bit, is 1, meaning this is a negative number.

0b0100 1111 (decimal 79)
invert all the bits
0b1011 0000
and add 1
0b1011 0001
Again, notice that the sign bit is one, so this is a negative number.

Before I tell you the big payoff we get for going to all this trouble to use two's complement, I'll tell you about the drawback, or rather the perceived drawback of doing this. If we have an 8-bit number, and we're using one of those bits to be the sign bit (in other words, that bit is tied up telling us whether the number is positive or negative, it can't tell us about the magnitude of the number any more), then we only have 7 bits left to tell us about the magnitude of the number. With 7 bits we can only represent positive numbers from 0-127, as opposed to the 0-255 we could represent with 8 bits.

So we have about half the positive numbers we had before, BUT we also have all the negative numbers, so it turns out we can represent just as many numbers with a "signed" binary number, it's just a different range of numbers than an "unsigned" binary number can represent. With a signed 8-bit number we have the positive numbers 1 to 127, the number 0, plus the negative numbers -1 to -128, for a total of 256 different numbers we can represent. It's kind of a weird thing that we can count 1 further into the negative numbers than we can count into the positive numbers when using a signed binary number. That's one of those weird things you just have to remember.

Okay, now we'll finally talk about the payoff. That multi-bit adder we designed many articles ago can be used, no problems, no modifications necessary, on signed two's complement numbers. That's it. That same adder we designed to add positive, unsigned-only, binary numbers can be used to add signed, two's complement numbers also, AND IT TREATS THEM CORRECTLY AS NEGATIVE NUMBERS. Holy crap, it's like magic. Seriously, when I first learned this I was like "yeah, but, there's no way that actually is true." Except it is.

In fact, it's so magical that we can just design one adder, and then we can use it to add any combination of positive or negative numbers together. We can add two positive numbers, two negative numbers, or one of each. Subtraction also becomes very easy. You just convert the number you want to subtract into a negative number (using the exact same process we did above), and then add it to the number you want to subtract from. BAM! Subtraction.

This article has already grown far too long, so I'm going to hold off on doing examples of subtraction until my next entry.