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

Looking at the two's complement system from a math point of view it really makes sense. In ten's complement, the idea is to essentially 'isolate' the difference.

Example: 63 - 24 = x

We add the complement of 24 which is really just (100 - 24). So really, all we are doing is adding 100 on both sides of the equation.

Now the equation is: 100 + 63 - 24 = x + 100, that is why we remove the 100 (or 10 or 1000 or whatever).

Due to the inconvenient situation of having to subtract one number from a long chain of zeroes, we use a 'diminished radix complement' system, in the decimal system, nine's complement.

When we are presented with a number subtracted from a big chain of nines, we just need to reverse the numbers.

Example: 99999 - 03275 = 96724

That is the reason, after nine's complement, we add 1. As you probably know from childhood math, 9 becomes 10 by 'stealing' 1. So basically it's just ten's complement that takes 1 from the difference.

In Binary, two's complement is equatable to ten's complement, while one's complement to nine's complement. The primary difference is that instead of trying to isolate the difference with powers of ten (adding 10, 100, etc. into the equation) we are trying to isolate the difference with powers of two.

It is for this reason that we invert the bits. Just like how our minuend is a chain of nines in decimal, our minuend is a chain of ones in binary.

Example: 111111 - 101001 = 010110

Because chains of ones are 1 below a nice power of two, they 'steal' 1 from the difference like nine's do in decimal.

When we are using negative binary number's, we are really just saying:

0000 - 0101 = x

1111 - 0101 = 1010

1111 + 0000 - 0101 = x + 1111

In order to 'isolate' x, we need to add 1 because 1111 is one away from 10000 and we remove the leading 1 because we just added it to the original difference.

1111 + 1 + 0000 - 0101 = x + 1111 + 1

10000 + 0000 - 0101 = x + 10000

Just remove 10000 from both sides to get x, it's basic algebra.

Answer 2

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

Answer 3

I liked lavinio's answer, but shifting bits adds some complexity. Often there's a choice of moving bits while respecting the sign bit or while not respecting the sign bit. This is the choice between treating the numbers as signed (-8 to 7 for a nibble, -128 to 127 for bytes) or full-range unsigned numbers (0 to 15 for nibbles, 0 to 255 for bytes).

Answer 4

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 (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 consider 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 positive 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 discern the decimal value is positive.

"One's compliment" negative numbers just flips the sign bit, then counts from 0. But this approach has to deal with interpreting 1000 as "negative zero" which is confusing. You generally only have to worry about this when working close to the hardware.

Answer 5

I read a fantastic explanation on Reddit by jng, using the odometer as an analogy.

It is a useful convention. The same circuits and logic operations that add / subtract positive numbers in binary still work on both positive and negative numbers if using the convention, that's why it's so useful and omnipresent.

Imagine the odometer of a car, it rolls around at (say) 99999. If you increment 00000 you get 00001. If you decrement 00000, you get 99999 (due to the roll-around). If you add one back to 99999 it goes back to 00000. So it's useful to decide that 99999 represents -1. Likewise, it is very useful to decide that 99998 represents -2, and so on. You have to stop somewhere, and also by convention, the top half of the numbers are deemed to be negative (50000-99999), and the bottom half positive just stand for themselves (00000-49999). As a result, the top digit being 5-9 means the represented number is negative, and it being 0-4 means the represented is positive - exactly the same as the top bit representing sign in a two's complement binary number.

Understanding this was hard for me too. Once I got it and went back to re-read the books articles and explanations (there was no internet back then), it turned out a lot of those describing it didn't really understand it. I did write a book teaching assembly language after that (which did sell quite well for 10 years).

Answer 6

You can also use an online calculator to calculate the two's complement binary representation of a decimal number: http://www.convertforfree.com/twos-complement-calculator/