Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why prefer two's complement over sign-and-magnitude for signed numbers?

It's done so that addition doesn't need to have any special logic for dealing with negative numbers. Check out the article on Wikipedia.

Say you have two numbers, 2 and -1. In your "intuitive" way of representing numbers, they would be 0010 and 1001, respectively (I'm sticking to 4 bits for size). In the two's complement way, they are 0010 and 1111. Now, let's say I want to add them.

Two's complement addition is very simple. You add numbers normally and any carry bit at the end is discarded. So they're added as follows:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 is 1, which is the expected result of "2+(-1)".

But in your "intuitive" method, adding is more complicated:

  0010
+ 1001
= 1011

Which is -3, right? Simple addition doesn't work in this case. You need to note that one of the numbers is negative and use a different algorithm if that's the case.

For this "intuitive" storage method, subtraction is a different operation than addition, requiring additional checks on the numbers before they can be added. Since you want the most basic operations (addition, subtraction, etc) to be as fast as possible, you need to store numbers in a way that lets you use the simplest algorithms possible.

Additionally, in the "intuitive" storage method, there are two zeroes:

0000  "zero"
1000  "negative zero"

Which are intuitively the same number but have two different values when stored. Every application will need to take extra steps to make sure that non-zero values are also not negative zero.

There's another bonus with storing ints this way, and that's when you need to extend the width of the register the value is being stored in. With two's complement, storing a 4-bit number in an 8-bit register is a matter of repeating its most significant bit:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1110 (negative two, in four bits)
11111110 (negative two, in eight bits)

It's just a matter of looking at the sign bit of the smaller word and repeating it until it pads the width of the bigger word.

With your method you would need to clear the existing bit, which is an extra operation in addition to padding:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1010 (negative two, in four bits)
10000010 (negative two, in eight bits)

You still need to set those extra 4 bits in both cases, but in the "intuitive" case you need to clear the 5th bit as well. It's one tiny extra step in one of the most fundamental and common operations present in every application.


Wikipedia says it all:

The two's-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract. This property makes the system both simpler to implement and capable of easily handling higher precision arithmetic. Also, zero has only a single representation, obviating the subtleties associated with negative zero, which exists in ones'-complement systems.

In other words, adding is the same, wether or not the number is negative.


Even though this question is old , let me put in my 2 cents.

Before I explain this ,lets get back to basics. 2' complement is 1's complement + 1 . Now what is 1's complement and what is its significance in addition.

Sum of any n-bit number and its 1's complement gives you the highest possible number that can be represented by those n-bits. Example:

 0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
 1111  (the highest number that we can represent by 4 bits)

Now what will happen if we try to add 1 more to the result. It will results in an overflow.

The result will be 1 0000 which is 0 ( as we are working with 4 bit numbers , (the 1 on left is an overflow )

So ,

Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)

Someone then decided to call 1's complement + 1 as 2'complement. So the above statement becomes: Any n'bit number + its 2's complement = 0 which means 2's complement of a number = - (of that number)

All this yields one more question , why can we use only the (n-1) of the n bits to represent positive number and why does the left most nth bit represent sign (0 on the leftmost bit means +ve number , and 1 means -ve number ) . eg why do we use only the first 31 bits of an int in java to represent positive number if the 32nd bit is 1 , its a -ve number.

 1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________

1 0000 (result is zero , with the carry 1 overflowing)

Thus the system of (n + 2'complement of n) = 0 , still works. The only ambiguity here is 2's complement of 12 is 0100 which ambiguously also represents +8 , other than representing -12 in 2s complement system.

This problem will be solved if positive numbers always have a 0 in their left most bit. In that case their 2's complement will always have a 1 in their left most bit , and we wont have the ambiguity of the same set of bits representing a 2's complement number as well as a +ve number.


Two's complement allows addition and subtraction to be done in the normal way (like you wound for unsigned numbers). It also prevents -0 (a separate way to represent 0 that would not be equal to 0 with the normal bit-by-bit method of comparing numbers).


this is to simplify sums and differences of numbers. a sum of a negative number and a positive one codified in 2's complements is the same as summing them up in the normal way.


Two's complement allows negative and positive numbers to be added together without any special logic.

If you tried to add 1 and -1 using your method
10000001 (-1)
+00000001 (1)
you get
10000010 (-2)

Instead, by using two's complement, we can add

11111111 (-1)
+00000001 (1) you get
00000000 (0)

The same is true for subtraction.

Also, if you try to subtract 4 from 6 (two positive numbers) you can 2's complement 4 and add the two together 6 + (-4) = 6 - 4 = 2

This means that subtraction and addition of both positive and negative numbers can all be done by the same circuit in the cpu.


The usual implementation of the operation is "flip the bits and add 1", but there's another way of defining it that probably makes the rationale clearer. 2's complement is the form you get if you take the usual unsigned representation where each bit controls the next power of 2, and just make the most significant term negative.

Taking an 8-bit value a7 a6 a5 a4 a3 a2 a1 a0

The usual unsigned binary interpretation is:
27*a7 + 26*a6 + 25*a5 + 24*a4 + 23*a3 + 22*a2 + 21*a1 + 20*a0
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

The two's complement interpretation is:
-27*a7 + 26*a6 + 25*a5 + 24*a4 + 23*a3 + 22*a2 + 21*a1 + 20*a0
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

None of the other bits change meaning at all, and carrying into a7 is "overflow" and not expected to work, so pretty much all of the arithmetic operations work without modification (as others have noted). Sign-magnitude generally inspect the sign bit and use different logic.