Two's complement
|
|
Two's complement is the most popular method of signifying negative integers in computers. 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.
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 27 − 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.
| Contents |
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 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)
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).
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 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 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 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!
Subtraction
Although subtraction could be done by taking the two's complement of the subtrahend and adding, this is rarely done in hardware since it would be more complicated than just building a subtractor. But 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)
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.
Why it works
The 2n possible values of n bits actually form a ring of equivalence classes, namely the integers modulo 2n, Z/(2n)Z. Each class represents a set {j + k·2n | k is an integer} for some integer j, 0 ≤ j ≤ 2n − 1. There are 2n such sets, and addition and multiplication are well-defined on them.
If the classes are taken to represent the numbers 0 to 2n − 1, and overflow ignored, then these are the unsigned integers. But each of these numbers is equivalent to itself minus 2n. So the classes could be understood to represent −2n−1 to 2n−1 − 1, by subtracting 2n from half of them.
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
Some special numbers to note are
| 127 | = | 0111 11112 |
| 64 | = | 0100 00002 |
| 1 | = | 0000 00012 |
| 0 | = | 0000 00002 |
| −1 | = | 1111 11112 |
| −64 | = | 1100 00002 |
| −127 | = | 1000 00012 |
| −128 | = | 1000 00002 |
fr:Complément à deux pl:Kod uzupełnień do dwóch fi:kahden komplementti