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

+14_{10} = 01110_{two's comp}

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

-01110_{two's comp} = 01110' + 1 = 10001 + 1
= 10010_{two's comp}

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
-2^{N-1}. Negating
1000 actually causes an overflow, since there is no
+2^{N-1} possible. The largest positive
value is +2^{N-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

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
2^{2} = 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

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 2^{N-1}-1.

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

**Table 14.11. Two's Complement Integer Ranges**

Bits | Range |
---|---|

8 | -2^{7} (-128) to
+2^{7}-1 (+127) |

16 | -2^{15} (-32,768) to
+2^{15}-1 (32,767) |

32 | -2^{31} (-2,147,483,648) to
+2^{31}-1 (+2,147,483,647) |

64 | -2^{63}
(-9,223,372,036,854,775,808) to
+2^{63}-1
(9,223,372,036,854,775,807) |

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

|---------------------------------|---------------------------------| Start anywhere in the positives Add the maximum negative value 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

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.

Negate two's complement 01101111.

Negate two's complement 00000000.

Perform the following conversions.

11111111 8-bit two's comp to decimal

01111111 8-bit two's comp to decimal

-7 decimal to 8-bit two's comp

-4_10 to two's comp

+12_10 to two's comp

8-bit two's complement 11111010 to decimal.

8-bit two's complement 00010011 to decimal.

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

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

0111, 0101

1110, 1101

0110, 1111

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.

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

01110010

11110010