Understanding Binary: Negative Numbers
Building on the previous article on Method of Complements, lets take a look at the difference between signed and unsigned integer types.
In the article on Primitive Data Types I mentioned that integers come in signed and unsigned flavors. Lets say we are working on 8-bit char's, the unsigned version will use all 8 bits for counting from 0 to 255, while the signed version will use 7 bits to count from 0 to 127, and the last bit to basically toggle that range to negative. (in actuality its from -128 to 127 as we will see soon)
Instead of simply toggling the last bit to make a positive number negative, computers use 2's complement.
Before we move on to 2's Compelement, we should learn 1's Complement. This is equivilant to learning 9's Complement before learning 10's Complement from the earlier post.
1's Complement is effectively the opposite of whatever the current bit holds, repeated for every bit.
In C (and similar languages) there is a handy operator to take any primitive type and compute the 1's complement. That is the Bitwise NOT operator: ~
~1101b = 0010b
~0111b = 1000b
Very easy stuff.
The rule for getting 2's Complement from 1's Complement, is the same for getting 10's Complement from 9's Complement in base 10 numbers. That is, 2's Complement is 1's Complement plus one. The same tricks apply as well, namely that all all rightmost 0's can stay 0, and simply add 1 to the first rightmost non-zero bit. (in practice the first rightmost 1 just stays 1 and you flip all the bits left of it)
In C (and similar languages) there is a handy operator to turn an integer type into the 2's complement (and is the subject of the article). That is the Unary Minus operator: -
-1101b = 0011b
-0111b = 1001b
-1100b = 0100b
Subtraction Using 2's Complement
Lets do a quick binary subtraction problem using 8-bit signed integers, 100-37 in decimal.
2's complement makes it:
Our final answer, 63 in base 10.
Now if you've been following along you may be wondering, why isn't the answer 0001 0011 1111b ?? Well in the Method of Complements, you need to do two things to get the correct answer.
1: Pad extra 0's in the higher order bits that may not be there (like 100-37 becomes 100-037) before you do the complementing.
2: Throw away the extra digit that is higher order than either of the starting numbers.
The beauty of working in fixed bit integer numbers, like in a computer, is that both of these rules are automatically followed. Every number has exactly 8-bits, so you don't need to pad. And the 'extra' 9'th bit doesn't fit in the memory space, and thus just dissapears.
Storing negative numbers in their Complement versions has another advantage. Namely that addition and subtraction can become agnostic as to the sign of the operands. If you can add numbers, then adding a negative number is the exact same procedure. And subtraction is to just find the complement of the second number and then use what you have for addition. And by agnostic as to the sign, I mean that you don't need to worry about special cases like when you subtract using a negative number.
4 - (-3) = 4 + (-(-3) = 7
4 = 0100b
3 = 0011b
-3 = 1101b
--3 = 0011b
0100b + 0011b = 0111b (which is 7 by the way)