Why is two's complement used to represent negative numbers?

Question

I'm just curious if there's a reason why in order to represent -1 in binary, two's complement is used: flipping the bits and adding 1?

-1 is represented by 11111111 (two's complement) rather than (to me more intuitive) 10000001 which is binary 1 with first bit as negative flag.

Disclaimer: I don't rely on binary arithmetic for my job!

Answer 1

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 what we expected the result of "2+(-1)" to be.

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 a 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.

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

Two's complement is used because it is simpler to implement in circuitry and also does not allow a negative zero.

If there are x bits, two's complement will range from +(2^x/2+1) to -(2^x/2). One's complement will run from +(2^x/2) to -(2^x/2), but will permit a negative zero (0000 is equal to 1000 in a 4 bit 1's complement system).

Answer 6

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.

Answer 7

To expand on others answers:

In two's complement

• Adding is the same mechanism as plain positive integers adding.
• Subtracting doesn't change too
• Multiplication too!

Division does require a different mechanism.

All these are true because two's complement is just normal modular arithmetic, where we choose to look at some numbers as negative by subtracting the modulo.

Answer 8

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 a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀

The usual unsigned binary interpretation is:
2⁷a₇ + 2⁶a₆ + > 2⁵a₅ + 2⁴a₄ + 2³a₃ +2²a₂ + 2¹a₁ + 2⁰a₀
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

The two's complement interpretation is:
-2⁷a₇ + 2⁶a₆ + > 2⁵a₅ + 2⁴a₄ + 2³a₃ +2²a₂ + 2¹a₁ + 2⁰a₀
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

None of the other bits change meaning at all, and carrying into a₇ 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.

Answer 9

Well, your intent is not really to reverse all bits of your binary number. It is actually to subtract each its digit from 1. It's just a fortunate coincidence that subtracting 1 from 1 results in 0 and subtracting 0 from 1 results in 1. So flipping bits is effectively carrying out this subtraction.

But why are you finding each digit's difference from 1? Well, you're not. Your actual intent is to compute the given binary number's difference from another binary number which has the same number of digits but contains only 1's. For example if your number is 10110001, when you flip all those bits, you're effectively computing (11111111 - 10110001).

This explains the first step in the computation of Two's Complement. Now let's include the second step -- adding 1 -- also in the picture.

Add 1 to the above binary equation:

11111111 - 10110001 + 1

What do you get? This:

100000000 - 10110001

This is the final equation. And by carrying out those two steps you're trying to find this, final difference: the binary number subtracted from another binary number with one extra digit and containing zeros except at the most signification bit position.

But why are we hankerin' after this difference really? Well, from here on, I guess it would be better if you read the Wikipedia article.

Answer 10

You can watch Professor Jerry Cain from Stanford explaining the two's complement, in the second lecture (the explanation regarding the 2's complement starts around 13:00) in the series of lectures called Programming Paradigms available to watch from Standford's YouTube channel. Here's the link to the lecture series: http://www.youtube.com/view_play_list?p=9D558D49CA734A02.