Two's Complement

Date: 07/13/99 at 18:48:26
From: Thomas F. Corbin
Subject: Computer programming

What is two's complement and how is it used?

Date: 07/14/99 at 12:03:05
From: Doctor Peterson
Subject: Re: Computer programming

Hi Tom,

Basically, two's complement numbers are a way to encode negative 
numbers into ordinary binary, such that addition still works. It goes 
like this, using a single-byte number for simplicity:

binary:   0    1    2    3     125  126  127  128  129    253 254 255
          +----+----+----+-...--+----+----+----+----+--...--+---+---+
2's comp: 0    1    2    3     125  126  127 -128 -127     -3  -2  -1

This is most effective if you draw it in a circle, so that -1 is 
followed by 0. Essentially, the second half of the number line (255 
being the largest number that can be represented by 8 bits) is taken 
over for negative numbers. Whereas normally (for unsigned numbers) 
there is a break between 127 and 0, at which point in counting there 
is a carry into the missing ninth bit and you "wrap around" like an 
odometer, in signed numbers there is a break between 127 and -128, 
where there is a carry into the "sign bit." Rotate the circle and it 
looks like this:

binary:    128  129    253  254  255  0   1   2   3     125  126  127 
            +----+-...--+----+----+---+---+---+---+--...--+---+----+
2's comp: -128 -127    -3   -2   -1   0   1   2   3     125  126  127 

In binary, the negative numbers are those whose leftmost bit, called 
the sign bit, is 1; positive numbers look just like unsigned numbers:

    00000000 = 0
    00000001 = 1
    ...
    01111111 = 127
    10000000 = -128
    10000001 = -127
    ...
    11111110 = -2
    11111111 = -1

The system is called two's complement because the negative of a number 
is formed by complementing each bit (subtracting it from 1, the "one's 
complement") and then adding 1 to the result:

        11111111
    2 = 00000010
        --------
   -2 = 11111101 + 1 = 11111110

Because of the way the numbers are assigned, adding one in binary 
still adds one to the negative number; in fact, when you add one to 
-1, you get zero (ignoring the carry). To add any two signed numbers, 
you just add the binary values, and again ignore the carry, if any:

       2 = 00000010
    + -3 = 11111101
    ----   --------
      -1 = 11111111

      -2 =    11111110
    + -3 =    11111101
    ----      --------
      -5 = (1)11111011

There are other ways in which negative numbers can be represented, but 
this has become very popular because of the properties I've pointed 
out.

You can find more about this in our archives:

 http://mathforum.org/library/drmath/view/55733.html   

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/