2’s Complement, and the trick to negate it

October 15th, 2004 admin Posted in Tidbits |

“2’s complement” is an often heard phrase in the world of computers. It is a notation used to represent numbers to ease subtraction. The intuitive binary number notation only stays positive, adding higher powers of 2 to the number as you keep adding 1’s to the left of a number. The most intuitive way to denote a negative of a number is to place a “-” symbol to its left. So if in decimal -5 is negative of 5, why can we not live with -101 for negative 101 (101 is binary for decimal 5) in binary? We can, but this “-” symbol is an abstraction useful to think about the number. A computer, which can only identify a 1 or a 0 (a high or a low voltage), needs to represent the “-” symbol using a trick.The easy trick would be to have an understanding that the first bit of any binary-represented number would indicate if the number is positive or negative. So if a number starts with 1, that indicates that treat the rest of the number as a positive binary number and negate it. If the number starts with a 0 that indicates that the number is positive. Unfortunately every sane number starts with a 1. If a number starts with a 0, the 0 is simply ignored (not to mention it looks strange). So to represent decimal 5 as 101 is fine but to represent it as 0101 looks a little odd. So then the way to make this first-bit-1-for-negative scheme work we need to associate a place value for the sign-representing leftmost digit. So say we want our number system to be capable of representing all numbers from -12 to 12, we will need to use 4 bits at least, for 12 is 1100. And then we can say the fifth bit from the right will be used to represent sign. So 12 becomes 01100 and -12 becomes 11100. And one that fact is made understood 5 represented as 00101 does not look as questionable. This scheme has two representations for 0, 00000 and 10000. In this scheme therefore, out of the 32 unique arrangements possible using 5 bits, 15 represent positive numbers, 15 represent negative numbers and there are 2 representations for 0. This scheme is called the sign-magnitude representation.

Yet another way to represent the fact that a number is negative would be to again have an understanding that the number is a represented using a fixed and predetermined number of bits, the left most bit being 1 indicates negative and being 0 indicates positive, and that the way you flip a positive number is to flip each of its individual bits. The positive number starts off with a 0 as its highest order bit, by definition, and therefore the flip of all the bits flips this bit too and makes it negative. The fact that for every pattern of bits there is a unique flipped pattern, guarantees that we have a unique negative number for each positive number, that can be easily identified. So if we say we will use 5 bits to represent a number and 5 is 00101, -5 is 11010. How we recognize 11010 to be -5 is we notice the “-” from the first bit and notice the 5 by flipping the bits back and calculating the resulting value in decimal. Only one small glitch is that this representation provides two equally acceptable versions of 0, namely 00000 and 11111 (since 0 = -0). So at another level of abstraction, this just means that out of the 32 different patterns possible using 5 bits, this scheme has 15 positives, 15 negatives and 2 0’s. This scheme is called 1’s complement representation.

2’s complement is another notation where the first or leftmost bit actually represents a negative offset. The remaining bits work the same way as for normal positive binary numbers. So in the most intuitive notation, 101 means 1*2² + 1*2⁰, or 5, and in the 2’s complement notation 101 means -1*2² + 1*2⁰, or -3. This representation has a unique representation for 0 (00000) and a unique representation for 15 positives, and 16 negatives! That is because 10000 means -16! There is therefore no duplication and the 32 variations of the 5 bits represent 32 unique numbers. Instead of 3 bits say we want to use 4 bits to represent 5. 5 would then be represented as 0101.But what about -3? The leftmost bit needs to be 1 to give the number a negative offset. The offset is -2³ and that is -8. So to get the end value to be -3 we need the remaining three bits to value +5. So -3 in 4 bits is 1101. And this indicates the phenomenon called sign bit extension. 101 is -3 and extending the sign bit (the most significant bit) on the left by repeating it makes the number 1101, which still is -2! In 2’s complement notation, in general the sign bit may be extended to the left (i.e. repeated on the left) without changing the value of the number.

The trick to negate a 2s complement number is often taught as “flip all bits and add a 1″. What is happening here? Let’s give it a shot first. 3 is 011 in 3 bit 2’s complement representation. Flip the bits and we get 100. Add a 1 and we get 101, which we saw earlier was 2’s complement representation for -3. Why this works is pretty straightforward once we see what’s going on. When the bits of an n bit positive number N are flipped essentially we end up with a number of value 2ⁿ - N. Why?

N = 0 x_n-2 x_n-3 . . . x₀ (where x_i is 1 or 0)

-2^n-1 2^n-2 2^n-3 . . . 2⁰ (corresponding power of 2)

= 0.(-2^n-1) + x_n-2.2^n-2 + x_n-3.2^n-3 . . . + x₀.2⁰

= x_n-2.2^n-2 + x_n-3.2^n-3 . . . + x₀.2⁰

N’ = N flipped

= 1 x_n-2‘ x_n-3‘ . . . x₀‘

-2^n-1 2^n-2 2^n-3 . . . 2⁰ (corresponding power of 2)

= 1.(-2^n-1) + x_n-2‘.2^n-2 + x_n-3‘.2^n-3 . . . + x₀‘.2⁰

N + N’ = 1.(-2^n-1) + (x_n-2+x_n-2‘).2^n-2 + (x_n-3+x_n-3‘).2^n-3 . . . + (x₀+x₀‘).2⁰

= 1.(-2^n-1) + 1.2^n-2 + 1.2^n-3 + … + 1.2⁰

= 1.(-2^n-1) + (2^n-1 - 1)

That last reduction essentially is based on the observation that 111₂ = 1000₂ - 1 and so on.

Therefore

N + N’ = -1

Therefore rearranging,

N’ + 1 = -N