twos complement

1. The 2's complement number system is a common number system used for expressing signed numbers in binary. In this system, the most significant bit acquires a negative value. Thus, if the most significant bit is a "1", the entire number is negative. All other digits represent positive numbers. For example, if we have the bitstring:

   1000 1111

   We can determine the (decimal) value as follows:

   1. The most significant bit is a 1, so it is negative. It is in the 7th place, so it has an absolute value of 2⁷. Thus, the most significant bit contributes -2⁷ = -128.
   2. The next three bits are zero, so they contribute nothing to the value.
   3. The last four bits represent the number 15. Since they are not in the most significant bit's place, 15 is positive.
   4. We add up all the numbers to get: -128+15 = -113.

   Note that we can only represent numbers from -128 to 127. Or, in general, for a bitstring of length x bits we can represent numbers from -2^x-1 up to 2^x-1-1.
   

2. Or "to take the 2's complement", meaning to take the opposite of a 2's complement number. Using our example above, we perform the following procedure:

   1. Take the 1's complement or invert each bit => We get: 0111 0000.
   2. Add 1 => We get 0111 0001

   Determining the decimal value as above, we see that the resulting number is indeed +113.

---

Other things to see: infinity, unsigned.

Since it is well known that computers can only perform the mathematical operation known as addition, the implementation of subtract would require negative values. To store negative numbers in computers, the early engineers devised the mathematical method known as the two's complement. The two's complement arithmetic relies on the concepts of overflow and truncation, which means that our operation would cause bits to be created that could not be stored. Thankfully, this is desired.

To take the two's complement, simply take the one's complement and add one. This seems overly simple, but its quite amazing. The binary representation of 13 is 00001101, so to find -13, we need take the one's complement to achieve 11110010, and then add one, 11110011.

Note: Yes, 11110011 is also 243, but engineers decided that when dealing with integer representation, half of the numbers are positive, and half negative, thus the greatest positive number that can be stored in 8 bits is 01111111, or 127. 10000000 = -128.

Now, to show the genius of the two's complement, we'll observe 13 + (-13).

  0000 1101
+ 1111 0011
-----------
1 0000 0000

Since we cannot store a ninth digit in an eight bit representation, we get our desired result of zero.

Since two's complement has been so nicely explained by SoberSephiroth above, this is now a good spot to point out the following bit of fun involving infinite series:

Everybody knows that the infinite sum:

S = 1 + 1/2 + 1/4 + 1/8 + ...

is equal to 2. One way to see this immediately is to double it, so:

2S = 2 + 1 + 1/2 + 1/4 + ...

and then subtract. All the other terms cancel, leaving S = 2. But you have to be careful when you do this sort of thing to make sure the series you're manipulating all converge. Let's try that again with:

T = 1 + 2 + 4 + 8 + ...

now we double it again:

2T = 2 + 4 + 8 + 16 + ...

and subtracting we get T = -1, even though we know T is unbounded. Yikes!

There's a wonderful margin note in the book Concrete Mathematics by Graham, Knuth, and Patashnik (yes, that Knuth) where they talk about the sums above. Next to the yikes! result, it says: "Sure: 1 + 2 + 4 + 8 + ... is the "infinite precision" representation of the number -1, in a binary computer with infinite word size".

2's complement is simply arithmetic modulo 2ⁿ, where n is the number of bits you have. You can take any consecutive 2ⁿ numbers and claim your bits represent them, so just pick the numbers starting at -2^n-1. This explains why addition and and multiplication continue to work.

sockpuppet's fun example with the diverging infinite series is just an example of how natural p-adic numbers really are; here p=2.

Introduction

The most popular method for representing negative numbers in a binary system.

The Representation

Assume we're dealing with bytes. In a 2's complement system, positive numbers are represented as for a system without negative numbers. For example,

27 decimal = 0001 1011

Under the 2's complement rules, to represent -27, we invert each bit and add one. Thus -27 is

-27 decimal = 1110 0101

As you can see, the left most bit effectively acts as a sign bit (1 is negative, 0 is positive). This means that the effective range of a signed byte under the 2's complement system is -128 to 127 (-128 can be represented as 1000 0000).

Arithmetic Operations

The nice thing about the 2's complement system is that it makes it easy to do arithmetic operations on negative numbers just as you would if you were only using positive numbers (i.e. unsigned integers), unlike other representation systems. For instance, let's add the 27 and -27 from above.

  0001 1011 (27)
+ 1110 0101 (-27)
  ---------
  0000 0000 (0)

Starting from the rightmost (i.e. least significant) bit, 1+1 means the answer is set to 0 and we carry 1 leftwards. The next bit has a 1 for the positive representation, and combined with the carry over this creates another carry but leaves a zero behind. Doing this for the rest of the sum and discarding the end carry, we see that the result is zero.

Here's another example

  0011 0101 (53)
+ 1110 1110 (-18)
  ---------
  0010 0011 (35)

Multiplication and division under this system also follow the same computational rules as for their unsigned operations.

Two's Complement is a process used to interpret the bits of an integer value so that both positive and negative values can be stored in the same range of bits without confusion.

This can't be explained without step-by-step examples, so let's dive in, eh? I'll take it easy on you and just use single-byte integers (that's 8 bits).

First, some simple binary, just to make sure the explanation is thorough. Each digit (either 0 or 1) represents a power of 2. The right-most digit is that digit times 2⁰, the next digit is that digit times 2¹, and so on. Therefore:

00000001 = 1
00000010 = 2
00000011 = 2 + 1 = 3
00010110 = 16 + 4 + 2 = 22
00101010 = 32 + 8 + 2 = 42
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

This example is for what is called an unsigned integer, because it can't store negative values, only the positive range 0 to 255.

So what if we want to store negative values? That's where Two's Complement comes in. The idea was that in signed integers (that can store both positive and negative integers), the left-most bit signifies a positive value if it is 0, and a negative value if it is 1.

The highest positive value is then 01111111 (127), and the lowest value is 10000000 (-128). How does this work? I'll show you:

10010010 Here's the actual stored byte
01101101 First, we flip every bit
00000001 Then you add 1 to it, and get
01101110 This is 110, but we're dealing with a negative, so it's interpreted to -110

The same process is used to interpret a negative value into the stored binary value, like this:

00101010 Is 42, but we want to store -42, so we start with the plain positive value
11010101 We then flip it
00000001 And add 1, and get
11010110 And this is the final stored result of -42

So that's the basics of Two's Complement. Another bit of trivia is that signed integers, if you keep adding 1 (binarily), will rotate. You can start with 0, and work you way up to 127, but as soon as you add again, 01111111 rolls over to 10000000 (-128). Adding one again gives you 10000001 (-127), and then you're working your way up through the negative values to 11111111 (-1). Since the number of bits is limited, and doesn't increase. Adding 1 again doesn't give us a 9-bit value of 100000000, but is truncated to 8-bits and we get 00000000, which of course is 0.