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.

Solution 1

Two's complement is a clever way of storing integers so that common math problems are very simple to implement.

To understand, you have to think of the numbers in binary.

It basically says,

• for zero, use all 0's.
• for positive integers, start counting up, with a maximum of 2^{(number of bits - 1)}-1.
• for negative integers, do exactly the same thing, but switch the role of 0's and 1's and count down (so instead of starting with 0000, start with 1111 - that's the "complement" part).

Let's try it with a mini-byte of 4 bits (we'll call it a nibble - 1/2 a byte).

• 0000 - zero
• 0001 - one
• 0010 - two
• 0011 - three
• 0100 to 0111 - four to seven

That's as far as we can go in positives. 2³-1 = 7.

For negatives:

• 1111 - negative one
• 1110 - negative two
• 1101 - negative three
• 1100 to 1000 - negative four to negative eight

Note that you get one extra value for negatives (1000 = -8) that you don't for positives. This is because 0000 is used for zero. This can be considered as Number Line of computers.

Distinguishing between positive and negative numbers

Doing this, the first bit gets the role of the "sign" bit, as it can be used to distinguish between nonnegative and negative decimal values. If the most significant bit is 1, then the binary can be said to be negative, where as if the most significant bit (the leftmost) is 0, you can say the decimal value is nonnegative.

"Sign-magnitude" negative numbers just have the sign bit flipped of their positive counterparts, but this approach has to deal with interpreting 1000 (one 1 followed by all 0s) as "negative zero" which is confusing.

"Ones' complement" negative numbers are just the bit-complement of their positive counterparts, which also leads to a confusing "negative zero" with 1111 (all ones).

You will likely not have to deal with Ones' Complement or Sign-Magnitude integer representations unless you are working very close to the hardware.

Solution 2

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 two's 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!

Solution 3

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

Solution 4

2's complement is very useful for finding the value of a binary, however I thought of a much more concise way of solving such a problem(never seen anyone else publish it):

take a binary, for example: 1101 which is [assuming that space "1" is the sign] equal to -3.

using 2's complement we would do this...flip 1101 to 0010...add 0001 + 0010 ===> gives us 0011. 0011 in positive binary = 3. therefore 1101 = -3!

What I realized:

instead of all the flipping and adding, you can just do the basic method for solving for a positive binary(lets say 0101) is (2³ * 0) + (2² * 1) + (2¹ * 0) + (2⁰ * 1) = 5.

Do exactly the same concept with a negative!(with a small twist)

take 1101, for example:

for the first number instead of 2³ * 1 = 8 , do -(2³ * 1) = -8.

then continue as usual, doing -8 + (2² * 1) + (2¹ * 0) + (2⁰ * 1) = -3

Solution 5

Imagine that you have a finite number of bits/trits/digits/whatever. You define 0 as all digits being 0, and count upwards naturally:

00
01
02
..

Eventually you will overflow.

98
99
00

We have two digits and can represent all numbers from 0 to 100. All those numbers are positive! Suppose we want to represent negative numbers too?

What we really have is a cycle. The number before 2 is 1. The number before 1 is 0. The number before 0 is... 99.

So, for simplicity, let's say that any number over 50 is negative. "0" through "49" represent 0 through 49. "99" is -1, "98" is -2, ... "50" is -50.

This representation is ten's complement. Computers typically use two's complement, which is the same except using bits instead of digits.

The nice thing about ten's complement is that addition just works. You do not need to do anything special to add positive and negative numbers!

View more solutions

Comments

[Naaff]

Probably the best part of two's complement is how it simplifies math. Try adding 2 (0010) and -2 (1110) together and you get 10000. The most significant bit is overflow, so the result is actually 0000. Almost like magic, 2 + -2 = 0.

[Jörg W Mittag]

Another advantage besides easy addition and subtraction is that 2s complement only has one zero. If you were using a simple sign bit, say using 0001 to represent +1 and 1001 to represent -1, you would have two zeros: 0000 ("+0") and 1000 ("-0"). That's a real pain in the behind.

[Ashwin]

Upvote for it being to the point and also for explaining why the negative values have a larger range the positive ones. I came looking for the reason for the range difference.

[Koray Tugay]

Shouldn't you say "for negative integers, do exactly the same thing but count down and switch the role of 0's and 1's"

[Koray Tugay]

Best answer in my opinion.

[SSC]

The best way, I could understand 2's complement. After reading this, I could understand all answers to the above question.

[jimo]

This is method is mentioned in the book Computer Systems: A programmer's perspective.

[chanzerre]

This is a much faster way!

[Max Koretskyi]

yes, this one is pretty simple and explains the matter very good

[Codor]

This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post.

[Dmitry]

It's answer. The simplest. For me - the best one.

[Manohar Reddy Poreddy]

plus1 for link that has a explanation with circle

[Marcos Pereira]

I don't understand how adding one when converting both ways always leads to the same number. In my mind you would reverse the steps, or subtract one or something.

[Suraj Jain]

Awesome .Added extra parts of converting bits to negative integer.

[Xunie]

I think the integer overflow concept might be better explained if for the negatives we start counting at the lowest number. (That is: negative eight and count up again). This way the student might see why an integer overflow results in such arbitrary numbers.

[MarcusJ]

So, does 2's complement simply not use a sign bit at all?

[jonsno]

I like this answer! Explains how taking 2s complement and adding one works.

[RomanKousta]

Why add 1 to the complement?

[user188757]

I like this answer as well. Especially where you show how the negative number is figured. Here I thought the whole number was inverted, not just the MSB and then added back the other weighted values. Thank you, this solved my brain block

[NH.]

The sign bit is still valid (except perhaps for the case of 0, which isn't positive or negative), but you don't simply change the sign bit to negate a number (see below for negation).

[NH.]

Good job mentioning the oddball number that doesn't have an inverse. But what do we do about this? Do we just set the overflow flag if someone tries to invert it?

[Hiroki]

This answer should be used on Wikipedia.

[mckenzm]

To me, these look like binary values. Two's complement generally involves bitwise inversion and an addition. So not really explanatory other than explaining binary ? For a 32 bit 'fullword' 8000 up is -ve, sure. But what is the purpose from an ALU POV ?

[mckenzm]

@Zinan Xing think about the carry. This is a good answer. What can be confusing to many students picking this up is negating a negative also involves the same process, bitwise inversion and add one, rather than subtract one and then invert. Mostly because we want to re-use the same operation.

[mckenzm]

Even assembler would be too high level. Need to see a gate level schematic of addition logic. With T cycles. You are algorithmically correct.

[Rain]

But how does the computer for example know if 1101 is negative three and not 13?

[mgagnon]

@FatalError It depends on how many bits the number is represented. 1101 = -3 (4 bits) , but 00001101 = 13 (8 bits).

[Abhishek Pathak]

While other answers focus on the "how", this answer leads us gently with the "why". It helped me. Thanks!

[Geremia]

Excellent explanation of how 0 and 1 switch roles for representing negative numbers.

[CJay]

Note that, 2's complement does not use for floating points numbers. A simple representation of floating points is IEEE 754.

[supercat]

If a number ends with 11000...000, inverting it will yield 01000...000. Two's-complement notation is based on the idea that all digits to the left of the leftmost represented digit should have the same value as that digit, but when inverting a number whose representation is 1000...000, that won't be true.

[Adrian Mole]

This doesn't add anything to the information provided by other answers.

[Charlie Parker]

I think a useful comment on the answer would be why complement does not mean inverse. Also, starting counting at 1111 and that being -1 but then start counting on 0000 and that not being 1 is strange. Why not start counting at 1111 and let that be zero? Since the most natural "complementing" of digit meaning would have meant that 1110 is -1 but that is not the case and is really confusing.

[Charlie Parker]

I think this is a better explanation of what complements means: I think a comment that was helpful to me is that complement is similar to inverse but instead of giving 0 it gives 2^N (by definition) e.g. with 3 bits for the number A we want A+~A=2^N so 010 + 110 = 1000 = 8 which is 2^3. At least that clarifies what the word "complement" is suppose to mean here as it't not just the inverting of the meaning of 0 and 1.

[paxdiablo]

I'm going to upvote this based solely on the fact it got the apostrophes in the right place regarding ones' complement and two's complement :-) As Knuth himself points out, the former is complementing based on a series of ones, the latter complementing based on a single power of two. Twos' complement exists but I think that's for base-3 (or 4?) numbers, not binary.

[paxdiablo]

It should also be pointed out that both C cand C++ standards committees are currently in the process of adopting two's complement as the "one true ring", ditching sign/magnitude and ones' complement as "blessed" alternatives.

[paxdiablo]

Wow, it's been a long time since I've seen a speedo with both mph and kph. Australia switched over before I'd hit 10yo and I still remember having to remind the old man (slang: father) of the basic conversions when he tried to do 100mph in a 100kph zone :-)

[paxdiablo]

In any case, I think they stopped allowing the odo to roll back at some point. Disconnecting it from the car and using a drill to roll it back was a favourite trick of (some rather dodgy) people when trying to sell their cars with a lower mileage (funny how we still use that term, guess kilometerage never caught on).

[Ignorant]

Yep, you explained it better than the Wikipedia article.