Editing Two's complement (section)

==Arithmetic operations==

===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">
   0000 1111  (15)
 + 1111 1011  (−5)
 ===========
   0000 1010  (10)
</pre>

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

<pre style="width:25em">
   0000 0101  (  5)
 + 1111 0001  (−15)
 ===========
   1111 0110  (−10)
</pre>

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<sub>10</sub>.

The last two bits of the [[Carry flag|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:
<pre style="width:25em">
  0111   (carry)
   0111  (7)
 + 0011  (3)
 ======
   1010  (−6)  invalid!
</pre>
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<sub>2</sub> = 10<sub>10</sub> is outside the permitted range of −8 to 7. The result would be correct if treated as unsigned integer.

In general, any two {{mvar|N}}-bit numbers may be added ''without'' overflow, by first sign-extending both of them to {{math|''N'' + 1}} bits, and then adding as above. The {{math|''N'' + 1}} bits result is large enough to represent any possible sum ({{math|1=''N'' = 5}} two's complement 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 {{mvar|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 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:
<pre style="width:25em">
  11110 000   (borrow)
   0000 1111  (15)
 − 1111 1011  (−5)
 ===========
   0001 0100  (20)
</pre>
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:
<pre style="width:25em">
  11100 000   (borrow)
   0000 1111  (15)
 − 0010 0011  (35)
 ===========
   1110 1100  (−20)
</pre>
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 {{mvar|N}}-bit numbers requires {{math|2''N''}} bits to contain all possible values.<ref>Bruno Paillard. ''An Introduction To Digital Signal Processors'', Sec. 6.4.2. Génie électrique et informatique Report, Université de Sherbrooke, April 2004.</ref>

If the precision of the two operands using two's complement is doubled before the multiplication, direct multiplication (discarding any excess bits beyond that precision) will provide the correct result.<ref>{{cite web
 |url         = http://pages.cs.wisc.edu/~cs354-1/beyond354/int.mult.html
 |title       = Two's Complement Multiplication
 |date        = August 24, 2007
 |access-date  = April 13, 2015
 |author      = Karen Miller
 |website     = cs.wisc.edu
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20150213203512/http://pages.cs.wisc.edu/~cs354-1/beyond354/int.mult.html
 |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}}"):
<pre style="width:25em">
     00000110  (6)
 *   11111011  (−5)
 ============
          110
         1100
        00000
       110000
      1100000
     11000000
    x10000000
 + xx00000000
 ============
   xx11100010
</pre>
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:

* 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.<ref>{{cite book |first=John F. |last=Wakerly |title=Digital Design Principles & Practices |publisher=Prentice Hall |edition=3rd |year=2000 |page=47 |isbn=0-13-769191-2 }}</ref>

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 bit]]s 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 "|":
<pre style="width:90%;overflow:scroll;white-space:pre">
  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)
</pre>

===Comparison (ordering)===
[[Comparison (computer programming)|Comparison]] is often implemented with a dummy subtraction, where the flags in the computer's [[status register]] are checked, but the main result is ignored. The [[zero flag]] indicates if two values compared equal. If the exclusive-or of the [[Sign flag|sign]] and [[Overflow flag|overflow]] flags is 1, the subtraction result was less than zero, otherwise the result was zero or greater. These checks are often implemented in computers in [[conditional branch]] instructions.

Unsigned binary numbers can be ordered by a simple [[lexicographic ordering]], where the bit value 0 is defined as less than the bit value 1. For two's complement values, the meaning of the most significant bit is reversed (i.e. 1 is less than 0).

The following algorithm (for an {{mvar|n}}-bit two's complement architecture) sets the result register R to −1 if A < B, to +1 if A > B, and to 0 if A and B are equal:

<syntaxhighlight lang="pascal">
// reversed comparison of the sign bit

if A(n-1) = 0 and B(n-1) = 1 then
    return +1;
else if A(n-1) = 1 and B(n-1) = 0 then
    return -1
end;
 
// comparison of remaining bits

for i := n-2 downto 0 do begin
    if A(i) = 0 and B(i) = 1 then
        return -1
    else if A(i) = 1 and B(i) = 0 then
        return +1 
    end
end
 
return 0
</syntaxhighlight>