Recent Articles

Two's complement

Two's complement is a method of signifying negative numbers in binary. It is also an operation which may be applied to positive binary values in order to perform subtraction using the method of complements, effectively allowing subtraction of one binary number from another using only the addition operation. This is useful in microprocessors for which subtraction is unavailable or too complex to perform efficiently.

Signed binary numerals

Representing negative values in binary system can be done in many ways. One way is the sign of the number depends on the presence of a sign bit. In a signed binary numeral, the first bit indicates whether a numeral should be interpreted as a negative value or a positive value. If the first bit is 1, the numeral is negative; if the first bit is 0, the numeral is either positive or zero.

However this method has an unfortunate drawback, that in effect two digits for zero exist (-0 and +0), and that addition and subtraction becomes difficult relying purely on a sign bit.

For example, a signed 8-bit binary numeral uses the leftmost bit as the sign bit; the remaining seven bits indicate the value of the numeral. If the sign bit is 0, the remaining seven bits are interpreted according to the customary rules of the binary numeral system. If the sign bit is 1, then the remaining seven bits contain a numeral in two's complement form.

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

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:

This is because a positive value of 128 cannot be represented with a 8-bit signed binary numeral.

Using two's complement as the method for representing negative numbers allows us to have one digit for 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:

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:

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:

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:

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. Converting a negative number into its positive equivalent is carried out in the same way; 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:

Flip the bits of the second number:

and add one:

Now add the results to the first number:

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)

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: