Editing Two's complement (section)

==Converting to two's complement representation==
<!-- This section contains one footnote that is wrapped in a <ref></ref> tag, but this footnote does not list any external references or sources. -->
In two's complement notation, a ''non-negative'' number is represented by its ordinary [[Binary numeral system|binary representation]]; in this case, the most significant bit is 0. Though, the range of numbers represented is not the same as with unsigned binary numbers. For example, an 8-bit unsigned number can represent the values 0 to 255 (11111111). However a two's complement 8-bit number can only represent non-negative integers from 0 to 127 (01111111), because the rest of the bit combinations with the most significant bit as '1' represent the negative integers −1 to −128.

The two's complement operation is the [[additive inverse]] operation, so negative numbers are represented by the two's complement of the [[absolute value]].

===From the ones' complement===
To get the two's complement of a negative binary number, all [[bit]]s are inverted, or "flipped", by using the [[bitwise NOT]] operation; the value of 1 is then added to the resulting value, ignoring the overflow which occurs when taking the two's complement of 0.

For example, using 1 byte (=8 bits), the decimal number 5 is represented by
{{block indent|0000 0101<sub>2</sub>}}
The most significant bit (the leftmost bit in this case) is 0, so the pattern represents a non-negative value. To convert to −5 in two's-complement notation, first, all bits are inverted, that is: 0 becomes 1 and 1 becomes 0:
{{block indent|1111 1010<sub>2</sub>}}
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<sub>2</sub>}}
The result is a signed binary number representing the decimal value −5 in two's-complement form. The most significant bit is 1, signifying 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:
{{block indent|0000 0100<sub>2</sub>}}
And adding one gives the final value:
{{block indent|0000 0101<sub>2</sub>}}
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<sup>''N''</sup>===

The sum of a number and its ones' complement is an {{mvar|N}}-bit word with all 1 bits, which is (reading as an unsigned binary number) {{math|2<sup>''N''</sup> − 1}}. Then adding a number to its two's complement results in the {{mvar|N}} lowest bits set to 0 and the carry bit 1, where the latter has the weight (reading it as an unsigned binary number) of {{math|2<sup>''N''</sup>}}. Hence, in the unsigned binary arithmetic the value of two's-complement negative number {{math|''x''*}} of a positive {{mvar|x}} satisfies the equality {{math|1=''x''* = 2<sup>''N''</sup> − ''x''}}.{{efn|For {{math|1=''x'' = 0}} we have {{math|1=2<sup>''N''</sup> − 0 = 2<sup>''N''</sup>}}, which is equivalent to {{math|1=0* = 0}} modulo {{math|2<sup>''N''</sup>}} (i.e. after restricting to {{mvar|N}} least significant bits).}}

For example, to find the four-bit representation of −5 (subscripts denote the [[radix|base of the representation]]):
{{block indent|{{math|1=''x'' = 5<sub>10</sub>}} therefore {{math|size=120%|1=''x'' = 0101<sub>2</sub>}}}}
Hence, with {{math|1=''N'' = 4}}:
{{block indent|{{math|1=''x''* = 2<sup>''N''</sup> − ''x'' = 2<sup>4</sup> − 5<sub>10</sub> = 16<sub>10</sub> − 5<sub>10</sub> = 10000<sub>2</sub> − 0101<sub>2</sub> = 1011<sub>2</sub>}}}}
The calculation can be done entirely in base 10, converting to base 2 at the end:
{{block indent|{{math|1=''x''* = 2<sup>''N''</sup> − ''x'' = 2<sup>4</sup> − 5<sub>10</sub> = 11<sub>10</sub> = 1011<sub>2</sub>}}}}

===Working from LSB towards MSB===
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 (MSB) until the first&nbsp;1 is reached; then copy that&nbsp;1, and flip all the remaining bits (Leave the MSB as a 1 if the initial number was in sign-and-magnitude representation). This shortcut allows a person to convert a number to its two's complement without first forming its ones' complement. For example: in two's complement representation, the negation of "0011&nbsp;1100" is "1100&nbsp;0<u>100</u>", 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 LSB towards MSB method can be sped up by a similar logic transformation.