Mandalika's scratchpad [ Work blog @Oracle | My Music Compositions ]

Friday, January 07, 2005

2s complement

In general, we (human beings) express negative numbers by placing a minus (-) sign at the left end of the number. Similarly while representing the integers in binary format, we can leave the left-most bit be the sign bit. If the left-most bit is a zero, the integer is positive; if it is a one, it is negative. To make it easy to design computers which do integer arithmetic, integers should obey the following rules:

(1) Zero is positive and -0 = 0
(2) The top-most bit should tell us the sign of the integer.
(3) The negative of a negative integer is the original integer ie., --55 is 55.
(4) x - y should give the same result as x + -y. That is, 8 - 3 should give us the same result as 8 + -3.
(5) Negative and positive numbers shouldn't be treated in different ways when we do multiplication and division with them.

A simple and elegant way to represent integers which obeys these rules is called 2s complement. The 2s complement of an integer is calculated by changing all bits of integer from 1 to 0 & 0 to 1, then adding 1 to the result.

eg., The 2s complement of -55 is 1100 1001
```0011 0111 <- binary representation of 55 (8-bit)
1100 1000 <- the 1s complement; change 1's to 0's and 0's to 1's
+1
---------
1100 1001 <- the 2s complement (-55)
---------```
Now lets calculate --55 ie., 55
```1100 1001 <- binary representation of -55 (8-bit)
0011 0110 <- 1s complement of 55
+1
---------
0011 0111 = 55
---------```
Above example verifies rule (3); similarly we can verify rest of the rules