|
|
Two's ComplementTwo's complement is the most popular method of signifying negative numbers in binary. It is also an operation which may be applied to positive binary values in order to find the corresponding negative value. All processors have an "adder", used to add numbers together. The processor also uses that "adder" to subtract numbers using the method of complements. Nearly every computer system in existence today uses two's complement to represent signed integer values. 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 positive binary number. If the 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. 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 one's 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. Adding a numeral and its two's complement together produces zero: 11111 111 (carry) 0000 0101 (5) + 1111 1011 (-5) = 0000 0000 (0) 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 lost, resulting in the arithmetically correct result of 0. Ignoring this carry over is valid since we are only considering numbers that fall inside a given word size that the computer can handle. Since positive and negative two's complement numbers can be added in the same fashion, a subtracter for this representation can be constructed by performing a bitwise NOT of one of the inputs of an adder and sending a binary 1 to the carry input of the adder. An adder-subtracter can be made by using bitwise XOR with a control signal in place of the bitwise NOT and connecting that control signal to the carry-input of the adder. Converting a negative number into its positive equivalent is carried out in the same way: flip all the bits, and add 1. The two's complement of a negative numeral is the corresponding positive value. Subtraction To perform subtraction using two's complement you simply find the two's complement of the second number in the operation and then add the result to the first number. For example, in decimal terms we might say 35 - 15 = 20. A microprocessor might perform this operation in the following way: 0010 0011 (35) - 0000 1111 (15) = Flip the bits of the second number: 1111 0000 and add one: 1111 0001 Now add the results to the first number: 111 11 (carry) 0010 0011 (35) + 1111 0001 (-15) = 0001 0100 (20) Another example is a subtraction operation where the result is negative: 15 - 35 = -20 (the steps for taking the two's complement of 35 are not shown) 11 111 (carry) 0000 1111 (15) + 1101 1101 (-35) = 1110 1100 (-20) The last two bits of the carry row (reading right-to-left) contain vital information: whether the calculation resulted in an arithmetic overflow, e.g. 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 MSB of the result. In other terms, if the last two carry bits are 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: 111 (carry) 0111 (7) + 0011 (3) = 1010 (-6) invalid! 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. 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 | ||0111 11112 | | lign=right|64 | = | 0100 00002 | | lign=right|1 | = | 0000 00012 | | lign=right|0 | = | 0000 00002 | | lign=right| -1 | = | 1111 11112 | | lign=right| -64 | = | 1100 00002 | | lign=right| -127 | = | 1000 00012 | | lign=right| -128 | = | 1000 00002 |
|
 |