Monday, July 7, 2008

Negative Numbers Represented in C++

--------------------------------------------------------------------------------

You probably know that integers are represented in binary--in base 2. This is pretty straightforward for positive numbers, but it means you must choose an encoding for representing negatives. The encoding used by C++ (as well was by C and Java) is two's complement.
In two's complement, the first bit of a negative number is always 1. Otherwise, the number is 0 or postive. To find the bitstring representing a negative number, you take the bitstring representing the corresponding positive number and flip all the bits. Next, add 1 to the result.

In the following example, Ive used 4-bit numbers for simplicity:


-5d = -(0101b) = (1010b + 1b) = 1011b

Notice that -1d is represented as all 1's:

-1d = -(0001b) = 1110b + 1 = 1111b

A nice property of this encoding is that you can subtract by negating and then adding the following:

7d - 3d = 0111b
- 0011b

=> 0111b
+ 1100b + 1

=> 0111b
+ 1101b
= 0100b = 4d

Yet another nice property is that overflows and underflows wrap around and cancel one another out, like this:

5d + 6d = 0101b
+ 0110b
= 1011b
= -(0100b + 1)
= -0101b = -5d

If you subtract 6 from this result (by adding its negation), youll get 5 back. First, compute -6:

-6d = -(0110b) = 1001b + 1 = 1010b

Then, add -6d to -5d to get the original value:

1011b
+ 1010b
= 0101

Matthew Johnson

No comments: