CTCI-BIT

Two's Complement and Negative Number

A positive integer number is represented as itself while a negative number is presented as the two’s complement of its absolute value(with a 1 in its sign bit to indicate that a negative value). The two’s complement of an N-bit number(where N is the number of bits used for the number, excluding the signal bit) is the complement of the number with respect to $ 2^N$

Let’s look at the 4-bit integer -3 as an example. If it’s a 4-bit number, we have one bit for the sign and three bits for the value. We want the complement with respect to $2^3$ which is 8. The complement of 3 (the absolute value of -3) with respect to 8 is 5. 5 in binary is 101. Therefore, -3 in binary as a 4-bit number is 1101, with the first bit being the sign bit.

In other words,the binary representation of -K(negative K) as a N-bit number is concat(1, $ 2^N $-K).

Another way to look at this is that we invert the bits in the positive representation and then add 1. 3 is 011 in binary. Flip the bits to get 100, add 1 to get 101, then prepend the sign bit(1) to get 1101.

In a 4-bit integer, this would look like the following.

Observe that the absolute values of the integer on the left and right always sum to $2^3$, and that the binary values on the left and right sides are identical, other than the sign bit.