#### Two's Complement

##### Format

The most common format used to represent signed integers in modern computers is called two's complement. This is a slight variation on one's complement that turns out to be remarkably convenient to implement in hardware.

A positive integer in two's complement is the same as unsigned, sign-magnitude, and one's complement. It always has a 0 in the leftmost bit (sign bit).

+1410 = 01110two's comp

##### Negation

To negate a two's complement number, a process sometimes called taking the two's complement, we invert all the bits and add one.

-01110two's comp = 01110' + 1 = 10001 + 1 = 10010two's comp

### Caution

The term "two's complement" can refer to the binary format (representation) or the negative of a two's complement binary value (the two's complement of 1011 is 0101, and negating is sometimes called "taking the two's complement"). Watch out for this and use the context of the sentence to understand which one we're talking about.

I've often wondered if people who create this kind of confusion are just evil, and intent on making students suffer. However, we should never ascribe to malice what can be explained by incompetence.

In this text, if we want you to negate a value, we will say negate the value. The term "two's complement" refers to the binary number system.

One of the beauties of two's complement is that the same negation process works for both positive and negative numbers. We might think that to reverse a negation, we should subtract one and invert the bits, but doing that produces the exact same result as inverting and adding 1 again! Weird, huh?

10010 - 1 = 10001, 10001' = 01110
10010' = 01101, 01101 + 1 = 01110

More examples:

-(0001) = 1110 + 1 = 1111
-(1111) = 0000 + 1 = 0001
-(1110) = 0001 + 1 = 0010
-(0010) = 1101 + 1 = 1110
-(0000) = 1111 + 1 = 0000   Oops, that can't be right!
-(1000) = 0111 + 1 = 1000   Oops, that can't be right!

So what happened with the negation of 0000 and 1000? Well, by adding 1 after inverting, we trade in the redundant representations of 0 (0000 and 1111) in one's complement for one more negative value. 1111 becomes -1 instead of 0, 1110 becomes -2 instead of -1, and 1000 becomes -2N-1. Negating 1000 actually causes an overflow, since there is no +2N-1 possible. The largest positive value is +2N-1.

Convert the following 4-bit two's comp values to decimal:

0111 = +(1 + 2 + 4) = +7
1000 = -(0111 + 1) = -(1000) = -8
0110 = +(2 + 4) = +6
1001 = -(0110 + 1) = -0111 = -(1 + 2 + 4) = -7
1110 = -(0001 + 1) = -0010 = -2

##### Another Way to Look at Two's Complement

We can also view two's complement as the same as unsigned binary, with one exception: The leftmost bit represents the negation of what it normally would. For example, in 3-bit unsigned binary, bit 2 (the leftmost bit) would be 22 = 4. So, in two's complement, it's -4.

The remaining bits are treated as positive powers of 2, so we can actually convert negative values from two's complement to decimal without negating the whole number:

Binary  Unsigned         Two's comp
000     0 + 0 + 0 = 0    0 + 0 + 0 =  0
001     0 + 0 + 1 = 1    0 + 0 + 1 =  1
010     0 + 2 + 0 = 2    0 + 2 + 0 =  2
011     0 + 2 + 1 = 3    0 + 2 + 1 =  3
100     4 + 0 + 0 = 4   -4 + 0 + 0 = -4
101     4 + 0 + 1 = 5   -4 + 0 + 1 = -3
110     4 + 2 + 0 = 6   -4 + 2 + 0 = -2
111     4 + 2 + 1 = 7   -4 + 2 + 1 = -1

The other bizarre property of two's complement is that addition works exactly like unsigned addition, regardless of sign! This means a computer that uses two's complement to store signed integers can use the same adder circuit to do both signed and unsigned addition. Subtraction is done by simply negating and adding. Since a computer needs the ability to negate numbers anyway, no additional hardware is needed to support signed integers or subtraction. Two's complement is obviously part of a conspiracy among computer scientists to put electrical engineers out of work. And if you believe that, I can offer you a great deal on a bridge I own in Brooklyn, which was left to me by my late uncle.

Binary      Unsigned    two's comp
0 1
0101        5       +5
+   1001    +   9   +   -7
--------------------------------
1110       14       -2

##### Range

Two's complement essentially takes one bit away from the value for use as a sign bit. Half of the bit patterns represent negative values and half represent non-negative values.

The largest positive value in N-bit two's complement is 0111...111, which is 2N-1-1.

The smallest negative value in N-bit two's complement is 1000...000, which is -2N-1.

Table 14.11. Two's Complement Integer Ranges

BitsRange
8-27 (-128) to +27-1 (+127)
16-215 (-32,768) to +215-1 (32,767)
32-231 (-2,147,483,648) to +231-1 (+2,147,483,647)
64-263 (-9,223,372,036,854,775,808) to +263-1 (9,223,372,036,854,775,807)

##### Comparison

Comparison of two's complement values is the same as unsigned if the numbers have the same sign. If the signs are different, then the positive number is larger. We cannot use unsigned comparison if the signs differ. This is the one thing that two's complement does not do conveniently.

A       B       Unsigned    Two's comp
0111    0110    >           >
1111    1000    >           >
0111    1111    <           >

This is due to the fact that two's complement rearranges the binary patterns on the number line, so that the latter half of the patterns (those beginning with 1), are actually less than those in the first half. With unsigned integers, a value with a 1 in the leftmost bit is obviously greater than anything with a 0 there. The opposite is true for two's complement.

0        +7   -8       -1       Two's comp
0000 ... 0111 1000 ... 1111
0        +7   +8       +15      Unsigned

As we can see above, 1000 is greater than 0111 in unsigned binary, but less than in two's complement. Hence, we will need more circuitry for two's complement comparison.

##### Overflow Detection

Overflow in two's complement is indicated by a result with the wrong sign. I.e., if you add two positives and get a negative result, or add two negatives and get a positive.

### Note

It is not possible to get an overflow when adding numbers of opposite signs. Think of it this way. When adding a positive and a negative, we always move toward and possibly across the center of the number line, and we can at most move half the length of the number line, so we will never reach either end.
|---------------------------------|---------------------------------|
Start anywhere in the positives
and we still won't reach the
minimum value.

|---------------------------------|
Finish                            Start

Examples:

111
0111    +7      0111    +7      1111    -1
+   0011    +3      1000    -8      1000    -8
-----------------------------------------------------------------
1010    -6      1111    -1      0111    +7

OV              No OV           OV

##### Extension and Reduction

Two's complement values are extended to larger formats by simply copying the sign bit to all new positions, a process called sign extension.

4-bit       8-bit       16-bit              Decimal
0111        00000111    0000000000000111    +7
1110        11111110    1111111111111110    -2

To reduce a value to fewer bits, we have no choice but to simply remove the leftmost bits. Note that this is likely to change the value (effectively overflowing the smaller bit size). This is an unavoidable risk when truncating values.

### Note

Be sure to thoroughly review the instructions in Section 2, “Practice Problem Instructions” before doing the practice problems below.
1. Negate two's complement 01101111.

2. Negate two's complement 00000000.

3. Perform the following conversions.

1. 11111111 8-bit two's comp to decimal

2. 01111111 8-bit two's comp to decimal

3. -7 decimal to 8-bit two's comp

4. -4_10 to two's comp

5. +12_10 to two's comp

6. 8-bit two's complement 11111010 to decimal.

7. 8-bit two's complement 00010011 to decimal.

4. What is the range of a 10-bit two's complement value? Express the answer in binary and in decimal.

5. Indicate which of each pair of two's complement values below is greater.

1. 0111, 0101

2. 1110, 1101

3. 0110, 1111

6. What is the sum of two's complement values 0110 and 0011? Verify by converting the two terms and the sum to decimal. Was there an overflow? Explain in terms of the resulting bits.

7. Extend the following 8-bit two's complement values to 16 bits.

1. 01110010

2. 11110010