Two's complement: Encyclopedia - Two's complement

Two's complement

Two's complement is the most popular method of signifying negative integers in computer science. It is also an operation of negation (converting positive to negative numbers or vice versa) in computers which represent negative numbers using two's complement. Its use is ubiquitous today because it doesn't require the addition and subtraction circuitry to examine the signs of the operands to determine whether to add or subtract, making it both simpler to implement and capable of easily handling higher precision arithmetic. As well, 0 has only a single representation, obviating the subtleties associated with negative zero.

In the two's complement representation, the leftmost bit of a signed binary numeral indicates the sign. If the leftmost bit is 0, the number is interpreted as a non-negative binary number. If the most significant (leftmost) bit is 1, the bits contain a negative number in two's complement form. To obtain the absolute value of the negative number, all the bits are inverted then 1 is added to the result.

A signed 8-bit binary numeral can represent any integer in the range −128 to +127. If the sign bit is 0, then the largest value that can be stored in the remaining seven bits is 2⁷ − 1, or 127.

Using two's complement as the method for representing negative numbers allows us to have only one representation of zero, and to have effective addition and subtraction while still having the most significant bit as the sign bit.

Two's complement - Calculating two's complement

In finding the two's complement of a binary number, the bits are inverted, or "flipped", by using the bitwise NOT operation; the value of 1 is then added to the remaining numeral.

For example, beginning with the signed 8-bit binary representation of the decimal value 5:

0000 0101 (5)

The first bit is 0, so the numeral represented is indeed a positive 5. To convert to -5 in two's complement notation, the bits are inverted; 0 becomes 1, and 1 becomes 0:

1111 1010

At this point, the numeral is the ones' complement of the decimal value 5. To obtain the two's complement, 1 is added to the result, giving:

1111 1011 (−5)

The result is a signed binary numeral representing the decimal value −5 in two's complement form. The initial bit is 1, so the numeral is interpreted as a negative value.

The two's complement of a negative number is the corresponding positive value. For example, inverting the bits of −5 (above) gives:

0000 0100

And adding one gives the final value:

0000 0101 (5)

The decimal value of a two's complement binary number can be calculated by taking the value of the first bit, where the value is negative when the bit is one, and adding to it the values for each power of two where there is a one. Example:

1111 1011 (−5) = −128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 (−2^7 + 2^6 + ...)

Note that the two's complement of zero is itself: inverting gives all ones, and adding one changes the ones back to zeros (the overflow is ignored). Also the two's complement of the most negative number representable (e.g. a one as the sign bit and all other bits zero) ends up as itself after this procedure. If you are wondering why this happens, imagine a two's complement 4 bit signed integer - the most negative number's "positive counterpart" is occupied by "0", which gets classed as a positive number in this argument. Hence, there appears to be an 'extra' negative number.

A more formal definition of defining a two's complement negative number (denoted by N* in this example) is derived from the equation N * = 2ⁿ − N, where N is the corresponding positive number and n is the number of bits in the representation.

E.g. To find the 4 bit representation of -5:

N (base 10) = 5, therefore N (base 2) = 0101

n = 4

Hence:

N * = 2ⁿ − N = [2⁴]base2 − 0101 = 10000 − 0101 = 1011

N.B. You can also think of the equation as being entirely in base 10, converting to base 2 at the end, e.g.:

N * = 2ⁿ − N = 2⁴ − 5 = [11]base10 = [1011]base2

Obviously, "N* ... = 11" isn't strictly true but as long as you interpret that equals sign as "is represented by", it is perfectly acceptable to think of two's complements in this fashion.

Two's complement - Addition

Adding two's complement numbers does not require special processing if the operands have opposite signs, and the sign of the result is determined automatically. For example, adding 15 and -5:

 11111 111   (carry)
  0000 1111  (15)
+ 1111 1011  (-5)
===========
  0000 1010  (10)

This process is dependent upon the restriction to 8 bits of precision; a value of 1 is actually carried to the left, but this bit is ignored, resulting in the arithmetically correct result of 10.

The last two bits of the carry row (reading right-to-left) contain vital information: whether the calculation resulted in an arithmetic overflow, a number too large for the binary system to represent (in this case greater than 8 bits). An overflow condition exists when a carry (an extra 1) is generated into but not out of the far left sign bit, or out of but not into the sign bit. As mentioned above, the sign bit is the leftmost bit of the result.

In other terms, if the last two carry bits (the ones on the far left of the top row in these examples) are both 1's or 0's, the result is valid; if the last two carry bits are "1 0" or "0 1", an overflow has occurred. Conveniently, an XOR operation on these two bits can quickly determine if an overflow condition exists. As an example, consider the 4-bit addition of 7 and 3:

 0111   (carry)
  0111  (7)
+ 0011  (3)
=============
  1010  (−6)  invalid!

In this case, the far left two (MSB) carry bits are "01", which means there was a two's complement addition overflow.

Two's complement - Subtraction

Computers usually use the method of complements to implement subtraction. But although using complements for subtraction is related to using complements for representing signed numbers, they are independent; direct subtraction works with two's complement numbers as well. Like addition, the advantage of using two's complement is the elimination of examining the signs of the operators to determine if addition or subtraction is needed. For example, subtracting -5 from 15 is really adding 5 to 15, but this is hidden by the two's complement representation:

 11110 000   (borrow)
  0000 1111  (15)
− 1111 1011  (−5)
===========
  0001 0100  (20)

Overflow is detected the same way as for addition, by examining the leftmost bits of the borrow row; overflow occurred if they are different.

Another example is a subtraction operation where the result is negative: 15 − 35 = −20:

 11100 000   (borrow)
  0000 1111  (15)
− 0010 0011  (35)
===========
  1110 1100  (−20)

Two's complement - The weird number

With only one exception, when we start with any number in two's complement representation, if we flip all the bits and add 1, we get the two's complement representation of the negative of that number. Negative 12 becomes positive 12, positive 5 becomes −5, zero becomes zero, etc.

The most negative number in two's complement is sometimes called "the weird number" because it is the only exception.

The two's complement of the minimum number in the range will not have the desired effect of negating the number. For example, the two's complement of -128 results in the same binary number:

1000 0000  (−128)
0111 1111  (inverted bits)
1000 0000  (add one)

This is because a positive value of 128 cannot be represented with a 8-bit signed binary numeral. Note that this is detected as an overflow condition since there was a carry into but not out of the sign bit.

Although the number is weird, it is a valid number. All arithmetic operations work with it both as an operand and (unless there was an overflow) a result.

Two's complement - Sign extension

When turning a two's complement number with a certain number of bits into one with more bits (e.g., when copying from a 1 byte variable to a two byte variable), the sign bit must be repeated in all the extra bits. For example:

Some processors have instructions to do this in a single instruction. On other processors a conditional must be used followed with code to set the relevant bits or bytes.

Similarly, when a two's complement number is shifted to the right, the sign bit must be maintained. However when shifted to the left, a 0 is shifted in. These rules preserve the common semantics that left shifts multiply the number by two and right shifts divide the number by two.

Both shifting and doubling the precision are important for some multiplication algorithms. Note that unlike addition and subtraction, precision extension and right shifting are done differently for signed vs unsigned numbers.

Two's complement - Multiplication

The product of two n-bit numbers can potentially have 2n bits. If the precision of the two two's complement operands is doubled before the multiplication, direct multiplication (discarding any excess bits beyond that precision) will provide the correct result. For example, take 5 × −6 = −30. First, the precision is extended from 4 bits to 8. Then the numbers are multiplied, discarding the bits beyond 8 (shown by 'x'):

  00000101  (5)
× 11111010  (−6)
 =========
         0
      101
       0
    101
   101
  101
 x01
xx1
=========
xx11100010  (−30)

This is very inefficient; by doubling the precision ahead of time, all additions must be double-precision and at least twice as many partial products are needed than for the more efficient algorithms actually implemented in computers. Some multiplication algorithms are designed for two's complement, notably Booth's algorithm. Methods for multiplying sign-magnitude numbers don't work with two's complement numbers without adaptation. There isn't usually a problem when the multiplicand (the one being repeatedly added to form the product) is negative; the issue is setting the initial bits of the product correctly when the multiplier is negative. Two methods for adapting algorithms to handle two's complement numbers are common:

• First check to see if the multiplier is negative. If so, negate (i.e., take the two's complement of) both operands before multiplying. The multiplier will then be positive so the algorithm will work. And since both operands are negated, the result will still have the correct sign.

• Subtract the partial product resulting from the sign bit instead of adding it like the other partial products.

As an example of the second method, take the common add-and-shift algorithm for multiplication. Instead of shifting partial products to the left as is done with pencil and paper, the accumulated product is shifted right, into a second register that will eventually hold the least significant half of the product. Since the least significant bits are not changed once they are calculated, the additions can be single precision, accumulating in the register that will eventually hold the most significant half of the product. In the following example, again multiplying 5 by −6, the two registers are separated by "|":

 0101  (5)
×1010 (−6)
 ====|====
 0000|0000  (first partial product (rightmost bit is 0))
 0000|0000  (shift right)
 0101|0000  (add second partial product (next bit is 1))
 0010|1000  (shift right)
 0010|1000  (add third partial product: 0 so no change)
 0001|0100  (shift right)
 1100|0100  (subtract last partial product since it's from sign bit)
 1110|0010  (shift right, preserving sign bit, giving the final answer, −30)
 

Two's complement - Why it works

The 2ⁿ possible values of n bits actually form a ring of equivalence classes, namely the integers modulo 2ⁿ, Z/(2ⁿ)Z. Each class represents a set {j + k·2ⁿ | k is an integer} for some integer j, 0 ≤ j ≤ 2ⁿ − 1. There are 2ⁿ such sets, and addition and multiplication are well-defined on them.

If the classes are taken to represent the numbers 0 to 2ⁿ − 1, and overflow ignored, then these are the unsigned integers. But each of these numbers is equivalent to itself minus 2ⁿ. So the classes could be understood to represent −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1, by subtracting 2ⁿ from half of them (specifically [2ⁿ⁻¹, 2ⁿ−1]).

For example, with eight bits, the unsigned bytes are 0 to 255. Subtracting 256 from the top half (128 to 255) yields the signed bytes −128 to 127.

The relationship to two's complement is realised by noting that 256 = 255 + 1, and (255 − x) is the ones' complement of x.

Example

−95 modulo 256 is equivalent to 161 since

  1111 1111                       255 
− 0101 1111                     −  95   
===========                     =====
  1010 0000  (ones' complement)   160
+         1                     +   1
===========                     =====
  1010 0001  (two's complement)   161

Some special numbers to note are

Two's complement - Two's Complement and The Machine of the Universe

In a famous 1972 HAKMEM from the MIT AI Lab, Bill Gosper noted that whether or not a machine's internal representation was two's complement could be determined by summing the successive powers of two. In a flight of fancy, he noted that the result of doing this algebraically indicated that "algebra is run on a machine (the universe) which is twos-complement" [1].

However his reasoning is purely humor since Gosper uses a False Proof to get his result. His flawed step is 2X = X − 1 which isn't true at all but looks convincing when in the notation ...111 = ...110 + 1, implying an infinite and therefore equivalent string of ones. In reality the sum of powers of two would never repeat and you would run out of paper doing the calculations. By Gosper's logic, this indicates String or BigNum representation, which is precisely true since we write numbers as strings of Arabic Numerals. Neither Algebra nor the Universe have an intrinsic numeric representation and so Gosper's Method does not apply there, but interestingly, it does correctly detect the numeric representations of human calculators as well as electronic ones.

See also

• Method of complements

Adapted from the Wikipedia article "Two's complement", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki