How do you do negative numbers?

Signed magnitude
Use one bit for sign, 7 bits for number
Example: -1 (in an 8-bit system) could be 1000 0001 (base 2)

2's complement (most often used in computing)
Example: the 2's complement number representing -1 (in an 8-bit system) would be 1111 1111 (base 2)


What are complement numbers?

Consider odometer numbers on a bicycle:

Decimal examples

Odometer numbers are useful for both addition and subtraction (complements) of signed numbers.

- 2     + 998
+ 3     + 003
+ 1     1 001

In the second example, the correct result is just the +001; the overflow is ignored in fixed-length complement arithmetic.

Do subtraction as addition by using complements, i.e.
A - B = A + (-B)

Important: It is easier to compute -B and add than to subtract directly.

Example:

- 005     + 995
+ 003     + 997
+ 008     1 992

Note that 995 and 997 were added in the normal fashion, the overflow was ignored, and the result was 992, which can be converted from the complement (or odometer) system back to -8, the correct answer.

 signed   3-bit complement
     +3   003
     +2   002
     +1   001
      0   000
     -1   999
     -2   998
     -3   997
     -4   996
     -5   995
     -6   994
     -7   993
     -8   992

decimal   2's complement binary
   +127   01111111
   +126   01111110
   +125   01111101
    ...   ........
     +2   00000010
     +1   00000001
      0   00000000
     -1   11111111
     -2   11111110
    ...   ........
   -127   10000001
   -128   10000000

There are 256 numbers in an 8-bit fixed length 2's complement number system.
Why are these numbers called 2's complement?

M - N = M + (-N)
where -N is the complement of N.

Example:

decimal
    + 1   =     00000001
    - 1   =   + 11111111
      0   =   1 00000000

which does not equal 2^8, or 256; ignore the overflow, and the correct answer is zero.

Now we need an easy way to do 2's complement operations.

Example:

What is the representation of -27 (base 10) in 2's complement 8-bit notation?

  2^8 - 1     11111111
-      27   - 00011011
              11100100   corresponds to flipping all the bits;
                         also known as 1's complement
    add 1   + 00000001
   result     11100101   -27 in 2's complement representation

This approach is necessary because:
  1. Fixed-length nature of numbers stored in a computer
  2. More computationally efficient to implement a fast adder than an adder and a subtractor


Examples of 2's complement number operations

Addition and subtraction in 2's complement form

Examples:

decimal        binary           hex
    11   =     00001011   =     000B
  + 21   =   + 00010101   =   + 0015
    32   =     00100000   =     0020

    21   =     00010101   =     0015
  - 11   =   + 11110101   =   + FFF5
    10   =     00001010   =     000A

    11   =     00001011   =     000B
  - 21   =   + 11101011   =   + FFEB
  - 10   =     11110110   =     FFF6

  - 11   =     11110101   =     FFF5
  - 21   =   + 11101011   =   + FFEB
  - 32   =   1 11100000   =     FFE0

How we got the 2's complements of -11 and -21:

 11     00001011
~11   - 11110100   1's complement
+ 1   + 00000001   add 1
-11     11110101   2's complement representation

Algorithm

  1. Store N.
  2. Obtain ~N, the 1's complement of N, by replacing (bit by bit) every 0 with a 1 and vice versa in the number's binary representation.
  3. Add 1 and ignore any carry after the eighth bit.

Note: This algorithm works in hex by replacing each digit x with its hex complement, i.e. 15 - x. Example: The hex equivalent of 11 is $000B; its hex complement is then $FFF4, where each digit was computed as $F - x. Adding 1 to $FFF4 gives the result $FFF5 for the 2's complement of 11. (Using a dollar sign ($) before a number indicates that it is base 16.)

Example:

In binary:

 N     0000 0110 0100 0111
~N   - 1111 1001 1011 1000   1's complement
+1   + 0000 0000 0000 0001   add 1
-N     1111 1001 1011 1001   2's complement representation

In hex:

 N     0647
~N   - F9B8   1's complement
+1   + 0001   add 1
-N     F9B9   2's complement representation

A calculator will always give you the 2's complement directly.

The Most Significant Bit (MSB) is the binary digit corresponding to the largest power of 2 and is always 1 for a negative 2's complement number. As a result it is often called the sign bit.

In 2's complement, -0 = +0. Technically, 0 is the complement of itself.

 N     00000000
~N   - 11111111   1's complement
+1   + 00000001   add 1
-N     00000000   2's complement representation


Problems with fixed-length arithmetic

Overflow and underflow

For a 16-bit fixed-length number system,

Adding signed numbers can easily exceed these limits.

first digit
       0011   $3000
       0110   $6000
       1001   $9000

This result, from adding two positive numbers in the number system, results in $9000, which is larger than $7FFF, the largest allowed positive number. In fact, $9000 equals 1001 0000 0000 0000, which is a negative number. The sign of the result is different from that of the operands.

Rule: If there is a sign change in adding two positive 2's complement numbers, then overflow has occurred.

We can generalize these rules to signed addition and subtraction.

Sign extension

How about if numbers are of different length?

decimal   2's complement binary
          3-bit 4-bit  8-bit
     +3   011   0011   00000011
     +2   010   0010   00000010
     +1   001   0001   00000001
      0   000   0000   00000000
     -1   111   1111   11111111
     -2   110   1110   11111110
     -3   101   1101   11111101
     -4   100   1100   11111100

To extend a 2's complement number to a greater number of binary digits, you just continue the sign bit to the left.

Examples: Extend $9B to 16 bits.

$9B = 1001 1011 = 1111 1111 1001 1011 = $FF9B

Extend $5F to 16 bits.

$5F = 0101 1111 = 0000 0000 0101 1111 = $005F

Adding two 2's complement numbers of different length

43A0     43A0
  9B     FF9B   need to sign extend; you can't just add zeros.
????   1 433B

Note that the 8-bit $9B and the 16-bit $FF9B both represent -101 in their respective number systems.


Extracted from http://www.cwru.edu/4208000/cse/eeap/282/03_number_systems.html.