What is “2's Complement”?

Question

I'm in a computer systems course and have been struggling, in part, with Two's Complement. I want to understand it but everything I've read hasn't brought the picture together for me. I've read the wikipedia article and various other articles, including my text book.

Hence, I wanted to start this community wiki post to define what Two's Complement is, how to use it and how it can affect numbers during operations like casts (from signed to unsigned and vice versa), bit-wise operations and bit-shift operations.

What I'm hoping for is a clear and concise definition that is easily understood by a programmer.

Answer 1

Two complement is found out by adding one to 1'st complement of the given number. Lets say we have to find out twos complement of 10101 then find its ones complement, that is, 01010 add 1 to this result, that is, 01010+1=01011, which is the final answer.

Answer 2

Like most explanations I've seen, the ones above are clear about how to work with 2's complement, but don't really explain what they are mathematically. I'll try to do that, for integers at least, and I'll cover some background that's probably familiar first.

Recall how it works for decimal:
  2345
is a way of writing
  2 × 10³ + 3 × 10² + 4 × 10¹ + 5 × 10⁰.

In the same way, binary is a way of writing numbers using just 0 and 1 following the same general idea, but replacing those 10s above with 2s. Then in binary,
  1111
is a way of writing
  1 × 2³ + 1 × 2² + 1 × 2¹ + 1 × 2⁰
and if you work it out, that turns out to equal 15 (base 10). That's because it is
  8+4+2+1 = 15.

This is all well and good for positive numbers. It even works for negative numbers if you're willing to just stick a minus sign in front of them, as humans do with decimal numbers. That can even be done in computers, sort of, but I haven't seen such a computer since the early 1970's. I'll leave the reasons for a different discussion.

For computers it turns out to be more efficient to use a complement representation for negative numbers. And here's something that is often overlooked. Complement notations involve some kind of reversal of the digits of the number, even the implied zeroes that come before a normal positive number. That's awkward, because the question arises: all of them? That could be an infinite number of digits to be considered.

Fortunately, computers don't represent infinities. Numbers are constrained to a particular length (or width, if you prefer). So let's return to positive binary numbers, but with a particular size. I'll use 8 digits ("bits") for these examples. So our binary number would really be
  00001111
or
  0 × 2⁷ + 0 × 2⁶ + 0 × 2⁵ + 0 × 2⁴ + 1 × 2³ + 1 × 2² + 1 × 2¹ + 1 × 2⁰

To form the 2's complement negative, we first complement all the (binary) digits to form
  11110000
and add 1 to form
  11110001
but how are we to understand that to mean -15?

The answer is that we change the meaning of the high-order bit (the leftmost one). This bit will be a 1 for all negative numbers. The change will be to change the sign of its contribution to the value of the number it appears in. So now our 11110001 is understood to represent
  -1 × 2⁷ + 1 × 2⁶ + 1 × 2⁵ + 1 × 2⁴ + 0 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰
Notice that "-" in front of that expression? It means that the sign bit carries the weight -2⁷, that is -128 (base 10). All the other positions retain the same weight they had in unsigned binary numbers.

Working out our -15, it is
  -128 + 64 + 32 + 16 + 1
Try it on your calculator. it's -15.

Of the three main ways that I've seen negative numbers represented in computers, 2's complement wins hands down for convenience in general use. It has an oddity, though. Since it's binary, there have to be an even number of possible bit combinations. Each positive number can be paired with its negative, but there's only one zero. Negating a zero gets you zero. So there's one more combination, the number with 1 in the sign bit and 0 everywhere else. The corresponding positive number would not fit in the number of bits being used.

What's even more odd about this number is that if you try to form its positive by complementing and adding one, you get the same negative number back. It seems natural that zero would do this, but this is unexpected and not at all the behavior we're used to because computers aside, we generally think of an unlimited supply of digits, not this fixed-length arithmetic.

This is like the tip of an iceberg of oddities. There's more lying in wait below the surface, but that's enough for this discussion. You could probably find more if you research "overflow" for fixed-point arithmetic. If you really want to get into it, you might also research "modular arithmetic".

Answer 3

The simplest answer:

1111 + 1 = (1)0000. So 1111 must be -1. Then -1 + 1 = 0.

It's perfect to understand these all for me.

Answer 4

It is a clever means of encoding negative integers in such a way that approximately half of the combination of bits of a data type are reserved for negative integers, and the addition of most of the negative integers with their corresponding positive integers results in a carry overflow that leaves the result to be binary zero.

So, in 2's complement if one is 0x0001 then -1 is 0x1111, because that will result in a combined sum of 0x0000 (with an overflow of 1).

Answer 5

I wonder if it could be explained any better than the Wikipedia article.

The basic problem that you are trying to solve with two's complement representation is the problem of storing negative integers.

First consider an unsigned integer stored in 4 bits. You can have the following

0000 = 0
0001 = 1
0010 = 2
...
1111 = 15

These are unsigned because there is no indication of whether they are negative or positive.

Sign Magnitude and Excess Notation

To store negative numbers you can try a number of things. First, you can use sign magnitude notation which assigns the first bit as a sign bit to represent +/- and the remaining bits to represent the magnitude. So using 4 bits again and assuming that 1 means - and 0 means + then you have

0000 = +0
0001 = +1
0010 = +2
...
1000 = -0
1001 = -1
1111 = -7

So, you see the problem there? We have positive and negative 0. The bigger problem is adding and subtracting binary numbers. The circuits to add and subtract using sign magnitude will be very complex.

What is

0010
1001 +
----

?

Another system is excess notation. You can store negative numbers, you get rid of the two zeros problem but addition and subtraction remains difficult.

So along comes two's complement. Now you can store positive and negative integers and perform arithmetic with relative ease. There are a number of methods to convert a number into two's complement. Here's one.

Convert Decimal to Two's Complement

1. Convert the number to binary (ignore the sign for now) e.g. 5 is 0101 and -5 is 0101

2. If the number is a positive number then you are done. e.g. 5 is 0101 in binary using twos complement notation.

3. If the number is negative then

   3.1 find the complement (invert 0's and 1's) e.g. -5 is 0101 so finding the complement is 1010

   3.2 Add 1 to the complement 1010 + 1 = 1011. Therefore, -5 in two's complement is 1011.

So, what if you wanted to do 2 + (-3) in binary? 2 + (-3) is -1. What would you have to do if you were using sign magnitude to add these numbers? 0010 + 1101 = ?

Using two's complement consider how easy it would be.

 2  =  0010
 -3 =  1101 +
 -------------
 -1 =  1111

Converting Two's Complement to Decimal

Converting 1111 to decimal:

1. The number starts with 1, so it's negative, so we find the complement of 1111, which is 0000.

2. Add 1 to 0000, and we obtain 0001.

3. Convert 0001 to decimal, which is 1.

4. Apply the sign = -1.

Tada!