Saturday, September 15, 2012

Why 2's Complement

Say we have 3 bits to represent integers. We have 8 possible numbers.
000
001
010
011
100
101
110
111
We wish to use one of these eight numbers to represent 0, half to represent positive and half to represent negatives. But with eight of them, we cannot do justice both to positives and to negatives! Well we wish to represent 2 and -2 in such a way that 2+(-2) becomes zero even in our new representation.
Let us use 000 to represent 0. Say now we use 001 to represent 1. Then what could be a reasonable representation of -1 so that 1+(-1) = 0. In other words,
  001
+ xxx
-----
  000
Obviously xxx = 110, just flip the bits in 001. That almost worked, but what then does 111 mean? It must be the flipped version of 000 meaning 111 = -0, which is not good - we don't want negative zero. However, if we add 1 to 111, it becomes 000, the extra one falls off the left end because we just have 3 bits in our system. Ok. Then say our algorithm for representing negative number is as follows:
flip the bits in the positive number and then add 1 to the result of flipping.
Let's see what we get.
000 ---flip---> 111 + 1 = 000 (great! there is no negative 0)
001 ---flip---> 110 + 1 = 111 (= -1)
010 ---flip---> 101 + 1 = 110 (= -2)
011 ---flip---> 100 + 1 = 101 (= -3)
100 ---flip---> 011 + 1 = 100 (= -4)
So, we have got what we wanted, almost! And notice that all negative numbers have their left most bit set to 1. So, it is quite easy to recognize them in this representation. Say if the computer sees 110, it immediately knows 110 is a negative number as its left most bit is 1. Now to find out the magnitude of 110, all the computer needs to do is to apply the same two steps again:
110 ---flip---> 001 + 1 = 010 = 2. That means 110 = -2!
In this way we got one number as 0, four to be negatives and three to be positives and we can do subtraction using adding unit.
This flip and then add 1 is just 2's complement.

No comments:

Post a Comment