Two's complement

The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2^"N" for an "N"-bit two's complement).

A two's-complement system or two's-complement arithmetic is a system in which negative numbers are represented by the two's complement of the absolute value; [David J. Lilja and Sachin S. Sapatnekar, "Designing Digital Computer Systems with Verilog", Cambridge University Press, 2005 [http://books.google.com/books?vid=ISBN052182866X&id=5BvW0hYhxkQC&pg=PA37&lpg=PA37&ots=l-E0VjyPt8&dq=%22two%27s+complement+arithmetic%22&sig=sS5_swrfrzcQI2nHWest75sIjgg online] ] this system is the most common method of representing signed integers on computers. [E.g. "Signed integersare two’s complement binary values that can be used to represent both positive andnegative integer values.", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006] In such a system, a number is negated (converted from positive to negative or vice versa) by computing its two's complement. An N-bit two's-complement numeral system can represent every integer in the range −2^N-1 to +2^N-1-1.

The two's-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract. This property makes the system both simpler to implement and capable of easily handling higher precision arithmetic. Also, zero has only a single representation, obviating the subtleties associated with negative zero, which exists in ones'-complement systems.

The method of complements can also be applied in base-10 arithmetic, using ten's complements by analogy with two's complements.

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 and lower bits.

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.

The most negative 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 negative 5, zero becomes zero, etc.

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 in an 8-bit system results in the same binary number. This is because a positive value of 128 cannot be represented with an 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. This can lead to unexpected bugs in that a naive implementation of absolute value could return a negative number.

Although the number is an exception, it is a valid number in regular two's complement systems. All arithmetic operations work with it both as an operand and (unless there was an overflow) a result.

Why it works

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

If the classes are taken to represent the numbers 0 to 2^"n" − 1, and overflow ignored, then these are the unsigned integers. But each of these numbers is equivalent to itself minus 2^"n". So the classes could be understood to represent −2^"n"−1 to 2^"n"−1 − 1, by subtracting 2^"n" from half of them (specifically [2^"n"−1, 2^"n"−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

:−95 + 256:= −95 + 255 + 1:= 255 − 95 + 1:= 160 + 1:= 161

1111 1111 255 − 0101 1111 − 95 = =

1010 0000 (ones' complement) 160 + 1 + 1 = =

1010 0001 (two's complement) 161

Arithmetic operations

Addition

Adding two's-complement numbers requires no special processing if the operands have opposite signs: 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 depends upon restricting to 8 bits of precision; a carry to the (nonexistent) 9th most significant 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 both 0's, the result is valid; if the last two carry bits are "1 0" or "0 1", a sign 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. That is, "ten" is outside the permitted range of −8 to 7.

In general, any two "n"-bit numbers may be added "without" overflow, by first sign-extending both of them to "n"+1 bits, and then adding as above. The "n"+1 bit result is large enough to represent any possible sum (e.g. 5 bits can represent values in the range −16 to 15) so overflow will never occur. It is then possible, if desired, to 'truncate' the result back to "n" bits; the value is preserved if and only if the discarded bit is a proper sign extension of the retained result bits. This provides another method of detecting overflow — which is equivalent to the method of comparing the carry bits — but which may be easier to implement in some situations, since it does not require access to the internals of the addition.

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 operands 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 two leftmost (most significant) bits of the borrows; overflow has 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)

As for addition, overflow in subtraction may be avoided (or detected after the operation) by first sign-extending both inputs by an extra bit.

Multiplication

The product of two "n"-bit numbers can potentially have 2"n" 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 6 × −5 = −30. First, the precision is extended from 4 bits to 8. Then the numbers are multiplied, discarding the bits beyond 8 (shown by 'x'):

00000110 (6) × 11111011 (-5) =

110 110 0 110 110 110 x10 xx0 =

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 multiplication 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. This method requires the multiplicant's sign bit to be extended by one position, being preserved during the shift right actions. [John F. Wakerly, "Digital Design Principles & Practices", Prentice Hall, 3rd edition 2000, page 47]

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 6 by −5, the two registers and the extended sign bit are separated by "|":

0 0110 (6) (multiplicant with extended sign bit) × 1011 (-5) (multiplier) =|=|=

0|0110|0000 (first partial product (rightmost bit is 1)) 0|0011|0000 (shift right, preserving extended sign bit) 0|1001|0000 (add second partial product (next bit is 1)) 0|0100|1000 (shift right, preserving extended sign bit) 0|0100|1000 (add third partial product: 0 so no change) 0|0010|0100 (shift right, preserving extended sign bit) 1|1100|0100 ("subtract" last partial product since it's from sign bit) 1|1110|0010 (shift right, preserving extended sign bit)
1110|0010 (discard extended sign bit, giving the final answer, -30)

Two's complement and universal algebra

In the classic "HAKMEM" published by the MIT AI Lab in 1972, 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." [ [http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154 Hakmem - Programming Hacks - Draft, Not Yet Proofed ] ]

Gosper's end conclusion is not necessarily meant to be taken seriously, and it is akin to a mathematical joke. The critical step is "$...110\; =\; ...111\; -\; 1$", i.e., "$2X\; =\; X\; -\; 1$". This presupposes a method by which an infinite string of 1's is considered a number, which requires an extension of the finite place-value concepts in elementary arithmetic. It is meaningful either as part of a two's-complement notation for all integers, as a typical 2-adic number, or even as one of the generalized sums defined for the divergent series of real numbers 1 + 2 + 4 + 8 + · · ·. [For the summation of 1 + 2 + 4 + 8 + · · · without recourse to the 2-adic metric, see cite book |last=Hardy |first=G.H. |authorlink=G. H. Hardy |title=Divergent Series |year=1949 |publisher=Clarendon Press |id=LCC|QA295|.H29|1967 (pp.7-10)]

Potential ambiguities in usage

One should be cautious when using the term "two's complement", as it can mean either a number format or a mathematical operator. For example 0111 represents "7 in two's-complement notation," but 1001 is the "two's complement of 7," which is the "two's complement representation of –7." In code notation or conversation the statement "convert x to two's complement" may be ambiguous, as it could describe either the change in representation of x to two's-complement notation from some other format, or else (if the writer really meant "convert x to "its" two's complement") the calculation of the negated value of x.

ee also

*Division (digital), including restoring and non-restoring division in two's-complement representations
*Signed number representations
* [http://www.vb-helper.com/tutorial_twos_complement.html Tutorial: Two's Complement Numbers]

References

* Israel Koren, "Computer Arithmetic Algorithms", A.K. Peters (2002), ISBN 1-56881-160-8
* Ivan Flores, "The Logic of Computer Arithmetic", Prentice-Hall (1963)