Two's complement: Difference between revisions
10111100010 seems more correct to me; otherwise it should explain where 1111100010 comes from. Undid revision 474002285 by Incnis Mrsi (talk). |
No edit summary |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
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<sup>{{mvar|N}}</sup> for an {{mvar|N}}-[[bit]] two's complement). The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way. |
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<sup>{{mvar|N}}</sup> for an {{mvar|N}}-[[bit]] two's complement). The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way. |
||
A two's-complement system, or two's-complement [[arithmetic]], is a system in which [[signed number representations|negative numbers are represented]] by the two's complement of the absolute value;<ref>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]</ref> this system is the most common method of [[Signed number representations|representing signed integers]] on [[computer]]s.<ref>E.g. "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values.", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006</ref> In such a system, a number is negated (converted from positive to negative or vice versa) by computing its ones' complement and adding one. An {{mvar|N}}-bit two's-complement numeral system can represent every integer in the range −2<sup>{{mvar|N}}−1</sup> to 2<sup>{{mvar|N}}−1</sup>−1 while [[ones' complement]] can only represent integers in the range −(2<sup>{{mvar|N}}−1</sup>−1) to 2<sup>{{mvar|N}}−1</sup>−1 |
A two's-complement system, or two's-complement [[arithmetic]], is a system in which [[signed number representations|negative numbers are represented]] by the two's complement of the absolute value;<ref>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]</ref> this system is the most common method of [[Signed number representations|representing signed integers]] on [[computer]]s.<ref>E.g. "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values.", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006</ref> In such a system, a number is negated (converted from positive to negative or vice versa) by computing its ones' complement (i.e. its bitwise negation) and adding one. An {{mvar|N}}-bit two's-complement numeral system can represent every integer in the range −2<sup>{{mvar|N}}−1</sup> to 2<sup>{{mvar|N}}−1</sup>−1 while [[ones' complement]] can only represent integers in the range −(2<sup>{{mvar|N}}−1</sup>−1) to 2<sup>{{mvar|N}}−1</sup>−1 |
||
The two's-complement system has the advantage |
The two's-complement system has the advantage that the fundamental arithmetical operations of [[addition]], [[subtraction]] and [[multiplication]] are identical, regardless of whether the inputs and outputs are interpreted as unsigned binary numbers or two's complement (provided that [[arithmetic overflow|overflow]] is ignored). 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|ones'-complement systems]]. |
||
'''Two's complement''' is referred to as '''Binary Number Representation''' ('''BNR''') in protocols used in Aviation (e.g. [[ARINC 429]]). |
'''Two's complement''' is referred to as '''Binary Number Representation''' ('''BNR''') in protocols used in Aviation (e.g. [[ARINC 429]]). |
||
Line 10: | Line 10: | ||
<div class="thumb tright"><div style="width:20em;"> |
<div class="thumb tright"><div style="width:20em;"> |
||
{|class="wikitable sortable" style="text-align: center;" |
|||
{|style="width:100%; margin:0;" cellspacing="0" |
|||
! Bits |
|||
|align="right" style="background-color:#ddeeff;"| [[Most significant bit|Most<br />significant<br />bit]] ||align="right" colspan="9"| |
|||
! Unsigned value |
|||
! 2's complement value |
|||
|- |
|||
| 00000000 |
|||
| 0 |
|||
| 0 |
|||
|- |
|||
| 00000001 |
|||
| 1 |
|||
| 1 |
|||
|- |
|||
| 00000010 |
|||
| 2 |
|||
| 2 |
|||
|- |
|||
| 01111110 |
|||
| 126 |
|||
| 126 |
|||
|- |
|||
| 01111111 |
|||
| 127 |
|||
| 127 |
|||
|- |
|||
| 10000000 |
|||
| 128 |
|||
| -128 |
|||
|- |
|||
| 10000001 |
|||
| 129 |
|||
| -127 |
|||
|- |
|||
| 10000010 |
|||
| 130 |
|||
| -126 |
|||
|- |
|||
| 11111110 |
|||
| 254 |
|||
| -2 |
|||
|- |
|||
| 11111111 |
|||
| 255 |
|||
| -1 |
|||
|- |
|- |
||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''127''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''126''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''2''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''1''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''0''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''−1''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''−2''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''−127''' |
|||
|- |
|||
|align="right" style="width:2em; background-color:#ddeeff; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-left:1px solid #aaaaaa;"| '''1''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em; border-top:1px solid #aaaaaa; border-bottom:1px solid #aaaaaa; border-right:1px solid #aaaaaa;"| '''0''' |
|||
|align="right" style="width:2em;"| '''=''' ||align="right" style="width:2em;"| '''−128''' |
|||
|} |
|} |
||
{{caption|8-bit two's-complement integers}} |
{{caption|8-bit two's-complement integers}} |
Revision as of 16:57, 9 March 2012
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 2N for an N-bit two's complement). The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way.
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;[1] this system is the most common method of representing signed integers on computers.[2] In such a system, a number is negated (converted from positive to negative or vice versa) by computing its ones' complement (i.e. its bitwise negation) and adding one. An N-bit two's-complement numeral system can represent every integer in the range −2N−1 to 2N−1−1 while ones' complement can only represent integers in the range −(2N−1−1) to 2N−1−1
The two's-complement system has the advantage that the fundamental arithmetical operations of addition, subtraction and multiplication are identical, regardless of whether the inputs and outputs are interpreted as unsigned binary numbers or two's complement (provided that overflow is ignored). 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.
Two's complement is referred to as Binary Number Representation (BNR) in protocols used in Aviation (e.g. ARINC 429).
The method of complements can also be applied in base-10 arithmetic, using ten's complements by analogy with two's complements.
Bits | Unsigned value | 2's complement value |
---|---|---|
00000000 | 0 | 0 |
00000001 | 1 | 1 |
00000010 | 2 | 2 |
01111110 | 126 | 126 |
01111111 | 127 | 127 |
10000000 | 128 | -128 |
10000001 | 129 | -127 |
10000010 | 130 | -126 |
11111110 | 254 | -2 |
11111111 | 255 | -1 |
Explanation
Two's-complement numbers
Two's complement numbers is a way to encode negative numbers into ordinary binary, such that addition still works. Adding −1 + 1 should equal 0, but ordinary addition gives the result of 2 or −2 unless the operation takes special notice of the sign bit and performs a subtraction instead. Two's complement results in the correct sum without this extra step.
A two's-complement number system encodes positive and negative numbers in a binary number representation. The bits have a binary radix point and the bits are weighted according to the position of the bit within the array. A convenient notation is the big-endian ordering.[relevant?] In this notation, the bit to the left of the binary point has a bit index of 0 and a weight of 20. The bit indices increase, by one, to the left of the binary point, and decrease, by one, to the right of the binary point. The weight of each bit is a power of two, except for the left-most bit, whose weight is a negative power of two. With this bit numbering, the two's complement number (for a number w) with m integer bits and n fractional bits is represented by an array of bits (where the possible values 0 and 1 for each depends on w):
- .
The value of this number is given by the following formula.
The left-most bit, also called the most-significant bit (MSB), determines the sign of the number, but, unlike the sign-and-magnitude representation, also has a weight, −2m−1, as shown in the formula above. Because of this weight, it is misleading to call this bit the "sign bit".
The two's complement encoding shown above can represent the following range of numbers
Zero representation is
The biggest number is positive. Its value is
The smallest positive number (smallest absolute value) is
The smallest negative number is
The biggest negative number (smallest absolute value) is
Making the Two's Complement of a number
In two's complement, positive numbers are represented as binary numbers whose most significant bit . Negative numbers are represented with the most-significant bit , making use of the left-most bit's negative weight. All radix complement number systems use a fixed-width encoding. Every number encoded in such a system has a fixed width so the most-significant digit can be examined.
How to create algorithmically for the two's complement binary value ? (The algorithm is mainly due to )
- 1. Express the binary value for (important: express ALL coefficients )
- 2. If (the case is already finished by 1. since and for all , especially )
- 2a. Complement each (i.e. replace by for )
- 2b. Add the coefficient 1 (this 1 represents ) to the latest binary representation. The addition leads to the final representation for which is
- .
In general, for a radix r 's complement encoding, with r the base (radix) of the number system, an integer part of m digits and fractional part of n digits, then the r 's complement of a number 0≤x<r m−1 − r −n is determined by the formula:
x** = ( r m − x ) mod rm
The (r−1)'s complement of a number is determined by the formula:
x* = r m − r −n − x
We can also find the r 's complement of a number x by adding r −n to the (r−1)'s complement of the number:
x** = x* + r −n
Alternative conversion process
A shortcut to manually convert a binary number into its two's complement is to start at the least significant bit (LSB), and copy all the zeros (working from LSB toward the most significant bit) until the first 1 is reached; then copy that 1, and flip all the remaining bits. This shortcut allows a person to convert a number to its two's complement without first forming its ones' complement. For example: the two's complement of "0011 1100" is "1100 0100", where the underlined digits were unchanged by the copying operation (while the rest of the digits were flipped).
In computer circuitry, this method is no faster than the "complement and add one" method; both methods require working sequentially from right to left, propagating logic changes. The method of complementing and adding one can be sped up by a standard carry look-ahead adder circuit; the alternative method can be sped up by a similar logic transformation.
Sign extension
Decimal | 7-bit notation | 8-bit notation |
---|---|---|
−42 | 1010110 | 1101 0110 |
42 | 0101010 | 0010 1010 |
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 most-significant 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 most-significant bit, which contains magnitude and the sign information, 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.
−128 | 1000 0000 |
invert bits | 0111 1111 |
add one | 1000 0000 |
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 most-significant bit. This can lead to unexpected bugs in that a naive implementation of absolute value could return a negative number.
The most negative number in two's complement is sometimes called "the weird number," because it is the only exception.[3][4]
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
Given a set of all possible N-bit values, we can assign the lower (by binary value) half to be the integers from 0 to (2N−1−1) inclusive and the upper half to be −2N−1 to −1 inclusive. The upper half can be used to represent negative integers from −2N−1 to −1 because, under addition modulo 2N they behave the same way as those negative integers. That is to say that because i + j mod 2N = i + (j − 2N) mod 2N any value in the set { j + k2N | k is an integer } can be used in place of j.
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.
Decimal | Two's complement |
---|---|
127 | 0111 1111 |
64 | 0100 0000 |
1 | 0000 0001 |
0 | 0000 0000 |
−1 | 1111 1111 |
−64 | 1100 0000 |
−127 | 1000 0001 |
−128 | 1000 0000 |
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
Two's complement | Decimal |
---|---|
0111 | 7 |
0110 | 6 |
0101 | 5 |
0100 | 4 |
0011 | 3 |
0010 | 2 |
0001 | 1 |
0000 | 0 |
1111 | −1 |
1110 | −2 |
1101 | −3 |
1100 | −4 |
1011 | −5 |
1010 | −6 |
1001 | −7 |
1000 | −8 |
Fundamentally, the system represents negative integers by counting backward and wrapping around. The boundary between positive and negative numbers is arbitrary, but the de facto rule is that all negative numbers have a left-most bit (most significant bit) of one. Therefore, the most positive 4-bit number is 0111 (7) and the most negative is 1000 (−8). Because of the use of the left-most bit as the sign bit, the absolute value of the most negative number (|−8| = 8) is too large to represent. For example, an 8-bit number can only represent every integer from −128 to 127 (2(8−1) = 128) inclusive. Negating a two's complement number is simple: Invert all the bits and add one to the result. For example, negating 1111, we get 0000 + 1 = 1. Therefore, 1111 must represent −1.
The system is useful in simplifying the implementation of arithmetic on computer hardware. Adding 0011 (3) to 1111 (−1) at first seems to give the incorrect answer of 10010. However, the hardware can simply ignore the left-most bit to give the correct answer of 0010 (2). Overflow checks still must exist to catch operations such as summing 0100 and 0100.
The system therefore allows addition of negative operands without a subtraction circuit and a circuit that detects the sign of a number. Moreover, that addition circuit can also perform subtraction by taking the two's complement of a number (see below), which only requires an additional cycle or its own adder circuit. To perform this, the circuit merely pretends an extra left-most bit of 1 exists.
Calculating two's complement
In two's complement notation, a positive number is represented by its ordinary binary representation, using enough bits that the high bit (the sign bit) is 0. The two's complement operation is the negation operation, so negative numbers are represented by the two's complement of the representation of the absolute value.
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 resulting value. Bit overflow is ignored, which is the normal case with the zero value.
For example, beginning with the signed 8-bit binary representation of the decimal value 5, using subscripts to indicate the base of a representation needed to interpret its value:
The most significant bit is 0, so the pattern represents a non-negative (positive) value.
To convert to −5 in two's-complement notation, the bits are inverted; 0 becomes 1, and 1 becomes 0:
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:
The result is a signed binary number representing the decimal value −5 in two's-complement form. The most significant bit is 1, so the value represented is negative.
The two's complement of a negative number is the corresponding positive value. For example, inverting the bits of −5 (above) gives:
And adding one gives the final value:
The value of a two's-complement binary number can be calculated by adding up the power-of-two weights of the "one" bits, but with a negative weight for the most significant (sign) bit; for example:
Note that the two's complement of zero is zero: inverting gives all ones, and adding one changes the ones back to zeros (the overflow is ignored). Also the two's complement of the most negative number representable (e.g. a one as the most-significant bit and all other bits zero) is itself. Hence, there appears to be an 'extra' negative number.
A more formal definition of a two's-complement negative number (denoted by x* in this example) is derived from the equation , where x is the corresponding positive number and N is the number of bits in the representation.
For example, to find the 4 bit representation of −5:
- therefore
- N = 4
Hence:
The calculation can be done entirely in base 10, converting to base 2 at the end:
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 1010.
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 these last two bits are different from one another. As mentioned above, the sign of the number is encoded in the MSB of the result.
In other terms, if the left two carry bits (the ones on the far left of the top row in these examples) are both 1s or both 0s, the result is valid; if the left 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 signed 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, 10102 = 1010 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 while preserving the value 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, because it does not require access to the internals of the addition.
Subtraction
Computers usually use the method of complements to implement subtraction. Using complements for subtraction is closely related to using complements for representing negative numbers, since the combination allows all signs of operands and results; 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 0000 (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 requires 2N bits[citation needed] to contain all possible values. 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 1100 00000 110000 1100000 11000000 110000000 1100000000 ========== 10111100010 (−30)
NB:We only count the 8-form bit,by erasing the first numbers to making the 8-bit form Therefore:
00000110 (6) * 11111011 (−5) ============ 110 1100 00000 110000 1100000 11000000 x10000000 xx00000000 ============ xx11100010
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. Because both operands are negated, the result will still have the correct sign.
- Subtract the partial product resulting from the MSB (pseudo sign bit) instead of adding it like the other partial products. This method requires the multiplicand's sign bit to be extended by one position, being preserved during the shift right actions.[5]
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) (multiplicand 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."[6]
Gosper's end conclusion is not necessarily meant to be taken seriously,[by whom?] and it is akin to a mathematical joke. The critical step is "", i.e., "". This presupposes a method by which an infinite string of 1s 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 + · · ·.[7] Digital arithmetic circuits, idealized to operate with infinite (extending to positive powers of 2) bit strings, produce 2-adic addition and multiplication compatible with two's complement representation.[8] Continuity of binary arithmetical and bitwise operations in 2-adic metric also has some use in cryptography.[9]
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.
See also
- Division (digital), including restoring and non-restoring division in two's-complement representations
- Signed number representations
- p-adic numbers
- Ones' complement
- Offset binary
References
- ^ David J. Lilja and Sachin S. Sapatnekar, Designing Digital Computer Systems with Verilog, Cambridge University Press, 2005 online
- ^ E.g. "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values.", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006
- ^ Reynald Affeldt and Nicolas Marti. "Formal Verification of Arithmetic Functions in SmartMIPS Assembly" (PDF).
- ^ "Digital Design and Computer Architecture" by David Harris, David Money Harris, Sarah L. Harris. 2007. Page 18.
- ^ Wakerly, John F. (2000). Digital Design Principles & Practices (3rd ed.). Prentice Hall. p. 47. ISBN 0137691912.
- ^ Hakmem - Programming Hacks - Draft, Not Yet Proofed
- ^ For the summation of 1 + 2 + 4 + 8 + · · · without recourse to the 2-adic metric, see Hardy, G.H. (1949). Divergent Series. Clarendon Press. LCC QA295 .H29 1967. (pp. 7–10)
- ^ Vuillemin, Jean (1993). On circuits and numbers (PDF). Paris: Digital Equipment Corp. p. 19. Retrieved 2012-01-24.
{{cite book}}
: More than one of|pages=
and|page=
specified (help), Chapter 7, especially 7.3 for multiplication. - ^ Anashin, Vladimir; Bogdanov, Andrey; Kizhvatov, Ilya (2007). "ABC Stream Cipher". Russian State University for the Humanities. Retrieved 24 January 2012.
Further reading
- Koren, Israel (2002). Computer Arithmetic Algorithms. A.K. Peters. ISBN 1-56881-160-8.
- Flores, Ivan (1963). The Logic of Computer Arithmetic. Prentice-Hall.