Two's complement

From open-encyclopedia.com - the free encyclopedia.

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.

In the two's complement method, a signed binary numeral uses the leftmost bit as the sign bit and the remaining bits to indicate the value of the numeral. If the sign bit is 0, the remaining bits are interpreted according to the customary rules of the binary numeral system. If the sign bit is 1, the remaining 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:

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.

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:

0000 0101

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

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. 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:

  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!

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^n-1 to 2^n-1-1, by subtracting 2ⁿ 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 one's complement of x.

Eg.

-95 is equivalent to 161 since

-95 + 256

= -95 + 255 + 1

= 255 - 95 + 1

= 160 + 1

= 161

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

Some special numbers to note are

de:Zweierkomplement fi:kahden komplementti fr:Complément à deux