# 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
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
• Subtraction: To compute N1 - N2, add N1 to -N2

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