Two's complement: Difference between revisions

Revision as of 18:01, 31 January 2025

Latest revision as of 21:07, 19 August 2025

(15 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Mathematical operation on binary numbers, and a number representation based on this operation}}

'''Two's complement''' is the most common [[signed number representations|method of representing signed]] (positive, negative, and zero) [[Integer (computer science)|integers]] on computers,<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> and more generally, [[Fixed-point arithmetic|fixed point binary]] values. TwoAs with the [[ones's complement]] uses theand [[Mostsign-magnitude]] significantsystems, bit|binarytwo's digitcomplement withuses the ''greatest''[[most valuesignificant bit]] as the ''sign'' to indicate whetherpositive the(0) binaryor numbernegative is(1) positivenumbers, orand negative;nonnegative whennumbers theare [[mostgiven significanttheir bit]]unsigned isrepresentation ''1''(6 theis number0110, zero is signed0000); ashowever, negativein andtwo's whencomplement, thenegative mostnumbers significantare bitrepresented isby ''0''taking the number[[bit iscomplement]] signedof astheir positive.magnitude Asand athen result,adding non-negativeone numbers(−6 areis represented1010). asThe themselves:number 6of isbits 0110,in zerothe isrepresentation 0000,may andbe −6increased isby 1010padding (NOTall 6additional +high 1).bits Noteof thatpositive whileor thenegative numbernumbers ofwith binary1's bitsor is0's, fixedrespectively, throughoutor adecreased computationby itremoving isadditional otherwiseleading arbitrary.1's or 0's.

Unlike the [[ones' complement]] scheme, the two's complement scheme has only one representation for zero, with room for one extra negative number (the range of a 4-bit number is -8 to +7). Furthermore, the same arithmetic implementations can be used on signed as well as unsigned integers<ref>

{{cite book

|first1=Alexandre |last1=Bergel

Line 15:

}}

</ref>

and differ only in the integer overflow situations, since the sum of representations of a positive number and its negative is 0 (with the carry bit set).

== Procedure ==

Line 180:

At this point, the representation is the [[ones' complement]] of the decimal value −5. To obtain the two's complement, 1 is added to the result, giving:

{{block indent|1111 1011₂}}

The result is a signed binary number representing the decimal value −5 in two's-complement form. The most significant bit is 1, sosignifying that the value represented is negative.

Alternatively, instead of adding 1 after inverting a positive binary number, 1 can be subtracted from the number ''before'' it is inverted. The two methods can easily be shown to be equivalent. The inversion (ones' complement) of <math>x</math> equals <math>(2^N - 1) - x</math>, so the sum of the inversion and 1 equals <math>(2^N - 1) - x + 1 = </math><math>2^N - x - 1 + 1 = </math><math>2^N - x</math>, which equals the two's complement of <math>x</math> as expected. The inversion of <math>x - 1</math> equals <math>(2^N - 1) - (x - 1) = </math><math>(2^N - 1) - x + 1 = </math><math>2^N - x</math>, identical to the previous equation. Essentially, the subtraction inherent in the inversion operation changes the −1 added to <math>x</math> before the inversion into +1 added after the inversion. This alternate subtract-and-invert algorithm to form a two's complement can sometimes be advantageous in computer programming or hardware design, for example where the subtraction of 1 can be obtained for free by incorporating it into an earlier operation.<ref>... e.g. by reducing an added constant by 1, increasing a subtracted constant by 1, or setting the carry/borrow flag before a subtract-with-borrow operation. For example, to compute <math>-(m + 4)</math>, instead of adding 4 to <math>m</math>, inverting the result, and then adding 1, one can merely add 3 (= 4 − 1) to <math>m</math> and then invert the result. (Of course, it is also an option, using the invert-and-add scheme, to invert <math>m</math> first and then subtract 3 [equivalent to adding −3 = −4 + 1].)</ref>

The two's complement of a negative number is the corresponding positive value, except in the special case of the [[most negative number]]. For example, inverting the bits of −5 (above) gives:

Line 186 ⟶ 188:

And adding one gives the final value:

{{block indent|0000 0101₂}}

Likewise, the two's complement of zero is zero: inverting gives all ones, and adding one changes the ones back to zeros (since the overflow is ignored).

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 is an 'extra' negative number for which two's complement does not give the negation, see {{section link||Most negative number}} below.

The case for the most negative number is one of only two special cases. The other special case is for zero, the two's complement of which is zero: inverting gives all ones, and adding one changes the ones back to zeros (since the overflow is ignored). Mathematically, in the two's complement system of signed integers (which represents the negative of each number as its two's complement), this is obviously correct: the negative of 0 is in fact 0 (<math>-0 = 0</math>). This zero case also makes sense by the definition of two's complements: by that definition, the two's complement of zero would be <math>2^N - 0 = 2^N</math>, but in <math>N</math> bits, all values are taken modulo <math>2^N</math>, and <math>2^N</math>{{math|mod }}<math>2^N = 0</math>. In other words, the two's complement of 0 in <math>N</math> bits is (by definition) a single 1 bit followed by <math>N</math> zeros, but the 1 gets truncated, leaving 0.<ref>Zero is the one value which when added to its two's complement, using machine (modular) binary arithmetic, does not sum to <math>2^N</math>, but observe that in arithmetic modulo <math>2^N</math>, <math>0</math> is congruent to <math>2^N</math>.</ref>

In summary, the two's complement of any number, either positive, negative, or zero, can be computed in the same ways. In two's complement signed integer representation, the two's complement of any integer is equal to -1 times that integer, except for the most negative integer representable in the given number of bits <math>N</math>, i.e. the integer <math>-2^{N-1}</math>, the two's complement of which is itself (still negative).

===Subtraction from 2^''N''===

Line 353 ⟶ 357:

{{block indent|{{=}} 160. + 1.}}

{{block indent|{{=}} 161.}}

<div style="overflow-x: auto;">

<pre style="width:25em">

1111 1111 255.

Line 362 ⟶ 368:

1010 0001 (two's complement) 161.

</pre>

</div>

{|class="wikitable floatright" style="width:14em;text-align:center"

|+ Two's complement 4&nbsp;bit integer values

Line 406 ⟶ 414:

|series=Class notes for CS&nbsp;104

|publisher=Cornell University |department=Computer Science |place=Ithaca, New York

|url=httphttps://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html |access-date=2014-06-22

}}</ref>

Line 417 ⟶ 425:

===Addition===

Adding two's complement numbers requires no special processing even if the operands have opposite signs; the sign of the result is determined automatically. For example, adding 15 and −5:

<pre style="width:25em">

<div style="overflow-x: auto;">

<pre style="width:25em;">

0000 1111 (15)

+ 1111 1011 (−5)

Line 423 ⟶ 433:

0000 1010 (10)

</pre>

</div>

Or the computation of 5 − 15 = 5 + (−15):

<div style="overflow-x: auto;">

<pre style="width:25em">

0000 0101 ( 5)

Line 432 ⟶ 444:

1111 0110 (−10)

</pre>

</div>

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 10₁₀.

Line 438 ⟶ 451:

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:

<div style="overflow-x: auto;">

<pre style="width:25em">

0111 (carry)

Line 445 ⟶ 460:

1010 (−6) invalid!

</pre>

</div>

In this case, the far left two (MSB) carry bits are "01", which means there was a two's-complement addition overflow. That is, 1010₂ = 10₁₀ is outside the permitted range of −8 to 7. The result would be correct if treated as unsigned integer.

Line 451 ⟶ 468:

===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 whether 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:

<div style="overflow-x: auto;">

<pre style="width:25em">

11110 000 (borrow)

Line 458 ⟶ 477:

0001 0100 (20)

</pre>

</div>

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&nbsp;−&nbsp;35 = −20:

<div style="overflow-x: auto;">

<pre style="width:25em">

11100 000 (borrow)

Line 468 ⟶ 491:

1110 1100 (−20)

</pre>

</div>

As for addition, overflow in subtraction may be avoided (or detected after the operation) by first sign-extending both inputs by an extra bit.

Line 484 ⟶ 509:

|archive-date = February 13, 2015

}}</ref> For example, take {{math|1=6 × (−5) = −30}}. First, the precision is extended from four bits to eight. Then the numbers are multiplied, discarding the bits beyond the eighth bit (as shown by "{{Mono|x}}"):

<div style="overflow-x: auto;">

<pre style="width:25em">

00000110 (6)

Line 499 ⟶ 526:

xx11100010

</pre>

</div>

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 do not work with two's-complement numbers without adaptation. There is not 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: