Two's complement: Difference between revisions

Revision as of 11:12, 7 January 2025

Revision as of 00:39, 27 January 2025

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. Two's complement uses the [[Most Significantsignificant Bitbit|binary digit with the ''greatest'' value]] as the ''sign'' to indicate whether the binary number is positive or negative; when the [[most significant bit]] is ''1'' the number is signed as negative and when the most significant bit is ''0'' the number is signed as positive. As a result, non-negative numbers are represented as themselves: 6 is 0110, zero is 0000, and -6−6 is 1010 (NOT 6 + 1). Note that while the number of binary bits is fixed throughout a computation it is otherwise arbitrary.

Unlike the [[ones' complement]] scheme, the two's complement scheme has only one representation for zero. Furthermore, arithmetic implementations can be used on signed as well as unsigned integers<ref>

Line 26:

For example, to calculate the [[decimal]] number '''−6''' in binary from the number '''6''':

* Step 1: ''+6'' in decimal is ''0110'' in binary; the leftmost significant bit (the first 0) is the [[Sign (mathematics)|sign]] ''(just 110 in binary'' would be -2−2 in decimal).

* Step 2: flip all bits in ''0110'', giving ''1001''.

* Step 3: add the place value 1 to the flipped number ''1001'', giving ''1010''.

Line 61:

==Theory==

Two's complement is an example of a [[Method of complements|radix complement]].

The 'two' in the name refers to the term which, expanded fully in an {{mvar|N}}-bit system, is actually "two to the power of N" -– {{math|2^''N''}} (the only case where exactly 'two' would be produced in this term is {{math|''N'' {{=}} 1}}, so for a 1-bit system, but these do not have capacity for both a sign and a zero), and it is only this full term in respect to which the [[method of complements|complement]] is calculated. As such, the precise definition of the ''Twotwo's complement'' of an {{mvar|N}}-bit number is the [[method of complements|complement]] of that number with respect to {{math|2^''N''}}.

The defining property of being a ''complement to a number with respect to {{math|2^N}}'' is simply that the summation of this number with the original produce {{math|2^''N''}}. For example, using binary with numbers up to three- bits (so {{math|''N'' {{=}} 3}} and {{math|2^''N'' {{=}} 2³ {{=}} 8 {{=}} 1000₂}}, where '₂' indicates a binary representation), a two's complement for the number 3 ({{math|011₂}}) is 5 ({{math|101₂}}), because summed to the original it gives {{math|2³ {{=}} 1000₂ {{=}} 011₂ + 101₂}}. Where this correspondence is employed for representing negative numbers, it effectively means, using an analogy with decimal digits and a number-space only allowing eight non-negative numbers 0 through 7, dividing the number-space ininto two sets: the first four of the numbers 0 1 2 3 remain the same, while the remaining four encode negative numbers, maintaining their growing order, so making 4 encode -4−4, 5 encode -3−3, 6 encode -2−2 and 7 encode -1−1. A binary representation has an additional utility however, because the most significant bit also indicates the group (and the sign): it is 0 for the first group of non-negatives, and 1 for the second group of negatives. The tables at right illustrate this property.

{|class="wikitable sortable floatright" style="text-align: center;"

|+ Three-bit integers

Line 148:

| −1

|}

Calculation of the binary two's complement of a positive number essentially means subtracting the number from the {{math|2^''N''}}. But as can be seen for the three-bit example and the four-bit {{math|1000₂}} ({{math|2³}}), the number {{math|2^''N''}} will not itself be representable in a system limited to {{mvar|''N''}} bits, as it is just outside the {{mvar|''N''}} bits space (the number is nevertheless the reference point of the "Two's complement" in an {{mvar|''N''}}-bit system). Because of this, systems with maximally {{mvar|''N''}}-bits must break the subtraction into two operations: first subtract from the maximum number in the {{mvar|''N''}}-bit system, that is {{math|2^''N''-1−1}} (this term in binary is actually a simple number consisting of 'all 1s', and a subtraction from it can be done simply by inverting all bits in the number also known as [[Bitwise operation#NOT|the bitwise NOT operation]]) and then adding the one. Coincidentally, that intermediate number before adding the one is also used in computer science as another method of signed number representation and is called a [[Onesones' complement]] (named that because summing such a number with the original gives the 'all 1s').

Compared to other systems for representing signed numbers (''e.g.,'' [[ones' complement]]), the two's complement has the advantage that the fundamental arithmetic operations of [[addition]], [[subtraction]], and [[multiplication]] are identical to those for unsigned binary numbers (as long as the inputs are represented in the same number of bits as the output, and any [[integer overflow|overflow]] beyond those bits is discarded from the result). This property makes the system simpler to implement, especially for higher-precision arithmetic. Additionally, unlike ones' complement systems, two's complement has no representation for [[Signed zero|negative zero]], and thus does not suffer from its associated difficulties. Otherwise, both schemes have the desired property that the sign of integers can be reversed by taking the complement of its binary representation, but two's complement has an exception -– the lowest negative, as can be seen in the tables.<ref>{{cite book |author1first1=David J. |last1=Lilja |author2first1=Sachin S. |last1=Sapatnekar |title=Designing Digital Computer Systems with Verilog |publisher=Cambridge University Press |date=2005 |url=https://books.google.com/books?id=5BvW0hYhxkQC&dq=%22two%27s+complement+arithmetic%22&pg=PA37}}</ref>

==History==

Line 161:

The value&nbsp;{{mvar|w}} of an {{mvar|N}}-bit integer <math>a_{N-1} a_{N-2} \dots a_0</math> is given by the following formula:

:<math display="block">w = -a_{N-1} 2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i</math>

The most significant bit determines the sign of the number and is sometimes called the [[sign bit]]. Unlike in [[sign-and-magnitude]] representation, the sign bit also has the weight {{math|−(2^{''N'' − 1})}} shown above. Using {{mvar|N}} bits, all integers from {{math|−(2^{''N'' − 1})}} to {{math|2^{''N'' − 1} − 1}} can be represented.

==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]].

Line 174 ⟶ 176:

For example, using 1 byte (=8 bits), the decimal number 5 is represented by

:{{block indent|0000 0101₂}}

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₂}}

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, so the value represented is negative.

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₂}}

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

Line 194 ⟶ 196:

For example, to find the four-bit representation of −5 (subscripts denote the [[radix|base of the representation]]):

:{{block indent|{{math|1=''x'' = 5₁₀}} therefore {{math|size=120%|1=''x'' = 0101₂}}}}

Hence, with {{math|1=''N'' = 4}}:

:{{block indent|{{math|1=''x''* = 2^''N'' − ''x'' = 2⁴ − 5₁₀ = 16₁₀ -− 5₁₀ = 10000₂ − 0101₂ = 1011₂}}}}

The calculation can be done entirely in base 10, converting to base 2 at the end:

:{{block indent|{{math|1=''x''* = 2^''N'' − ''x'' = 2⁴ − 5₁₀ = 11₁₀ = 1011₂}}}}

===Working from LSB towards MSB===

Line 208 ⟶ 210:

{{Main|Sign extension}}

{|class="wikitable floatright" style="margin-left: 1.5em;text-align:center"

|+ Sign-bit repetition in 7- and 8-bit integers using two's complement

|-

Line 215 ⟶ 217:

!8-bit notation

|-

|alignstyle="text-align:right"| −42 ||align="center"| 1010110 ||align="center"| 1101 0110

|-

|alignstyle="text-align:right"| 42 ||align="center"| 0101010 ||align="center"| 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 one-byte variable to a two-byte variable), the most-significant bit must be repeated in all the extra bits. Some processors do this in a single instruction; on other processors, a conditional must be used followed by code to set the relevant bits or bytes.

Similarly, when a number is shifted to the right, the most-significant bit, which contains the sign information, must be maintained. However, when shifted to the left, a bit is shifted out. These rules preserve the common semantics that left shifts multiply the number by two and right shifts divide the number by two. However, if the most-significant bit changes from 0 to 1 (and vice versa), overflow is said to occur in the case that the value represents a signed integer.

Both shifting and doubling the precision are important for some multiplication algorithms. Note that unlike addition and subtraction, width extension and right shifting are done differently for signed and unsigned numbers.

Line 229 ⟶ 231:

With only one exception, starting with any number in two's-complement representation, if all the bits are flipped and 1 added, the two's-complement representation of the negative of that number is obtained. Positive&nbsp;12 becomes negative&nbsp;12, positive&nbsp;5 becomes negative&nbsp;5, zero becomes zero(+overflow), etc.

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

|+ <span class="anchor" id="−128_example_anchor">The two's complement of {{math| −128 }}</span>

|-

|align="center"| {{math| −128 }} || align="center"| 1000 0000

|-

|align="center"| invert bits || align="center"| 0111 1111

|-

|align="center"| add one ||align="center"| 1000 0000

|-

|colspan="2;" | {{center|{{small|Result is the same 8&nbsp;bit binary number.}}}}

|}

Taking the two's complement (negation) of the minimum number in the range will not have the desired effect of negating the number. For example, the two's complement of {{math| −128 }} in an eight-bit system is {{math| −128&nbsp;,}} as shown in the [[#−128_example_anchor|table to the right]]. Although the expected result from negating {{math| −128 }} is {{math| +128&nbsp;,}} there is no representation of {{math| +128 }} with an eight&nbsp;bit two's&nbsp;complement system and thus it is in fact impossible to represent the negation. Note that the two's complement being the same number is detected as an overflow condition since there was a carry into but not out of the most-significant bit.

Having a nonzero number equal to its own negation is forced by the fact that zero is its own negation, and that the total number of numbers is even. Proof: there are {{math| 2^n -− 1}} nonzero numbers (an odd number). Negation would partition the nonzero numbers into sets of size 2, but this would result in the set of nonzero numbers having even cardinality. So at least one of the sets has size 1, i.e., a nonzero number is its own negation.

The presence of the most negative number can lead to unexpected programming bugs where the result has an unexpected sign, or leads to an unexpected overflow exception, or leads to completely strange behaviors. For example,

* the unary negation operator may not change the sign of a nonzero number. e.g., {{math| −(−128) &nbsp;⟼&nbsp; −128 &nbsp;}} (where "{{math|⟼}}" is read as "becomes").

* an implementation of [[absolute value]] may return a negative number;<ref>

{{cite web

Line 254 ⟶ 256:

|url=http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html

}}

</ref> e.g., {{math|&nbsp; abs(−128) &nbsp;⟼&nbsp; −128&nbsp;.}}

* Likewise, multiplication by {{math| −1 }} may fail to function as expected; e.g., &nbsp; {{math| (−128) × (−1) &nbsp;⟼&nbsp; −128&nbsp;.}}

Line 261 ⟶ 263:

|first=John |last=Regehr

|year=2013

|title=Nobody expects the Spanish inquisition, or INT_MIN to be divided by -1−1

|website=Regehr.org |type=blog

|url=https://blog.regehr.org/archives/887

Line 279 ⟶ 281:

In the [[C (programming language)|C]] and [[C++]] programming languages, the above behaviours are [[Undefined behavior|undefined]] and not only may they return strange results, but the compiler is free to assume that the programmer has ensured that undefined numerical operations never happen, and make inferences from that assumption.<ref name=int32-c/> This enables a number of optimizations, but also leads to a number of strange bugs in programs with these undefined calculations.

This most negative number in two's&nbsp;complement is sometimes called ''"the weird number"'', because it is the only exception.<ref>

{{cite report

|first1=Reynald |last1=Affeldt

Line 307 ⟶ 309:

==Why it works==

Given a set of all possible {{mvar|N}}-bit values, we can assign the lower (by the binary value) half to be the integers from 0 to {{math|(2^{''N'' − 1} − 1)}} inclusive and the upper half to be {{math|−2^{''N'' − 1}}} to −1 inclusive. The upper half (again, by the binary value) can be used to represent negative integers from {{math|−2^{''N'' − 1}}} to −1 because, under addition modulo {{math|2^''N''}} they behave the same way as those negative integers. That is to say that, because {{math|1= ''i'' + ''j'' mod 2^''N'' = ''i'' + (''j'' + 2^''N'') mod 2^''N''}}, any value in the set {{math|1= { ''j'' + ''k'' 2^''N'' {{!}} ''k'' is an integer } }} can be used in place of&nbsp;{{mvar|j}}.<ref>{{cite web

| url = http://www.cs.uwm.edu/~cs151/Bacon/Lecture/HTML/ch03s09.html

| title = 3.9. Two's Complement | work = Chapter 3. Data Representation

Line 326 ⟶ 328:

!Binary (8-bit)

|-

|alignstyle="text-align:right"| 127 ||0111 1111

|-

|alignstyle="text-align:right"| 64 ||0100 0000

|-

|alignstyle="text-align:right"| 1  ||0000 0001

|-

|alignstyle="text-align:right"| 0  ||0000 0000

|-

|alignstyle="text-align:right"| −1 ||1111 1111

|-

|alignstyle="text-align:right"| −64 ||1100 0000

|-

|alignstyle="text-align:right"| −127 ||1000 0001

|-

|alignstyle="text-align:right"| −128 ||1000 0000

|}

===Example===

:''{{hatnote|In this subsection, decimal numbers are suffixed with a decimal point "."''}}

For example, an 8&nbsp;bit number can only represent every integer from &minus;128−128. to 127., inclusive, since {{math|(2^8 − 1 {{=}} 128.)}}. {{nowrap|−95. modulo 256.}} is equivalent to 161. since

:{{block indent|−95. + 256.}}

:{{block indent|= −95. + 255. + 1}}

:{{block indent|= 255. − 95. + 1}}

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

:{{block indent|= 161.}}

<pre style="width:25em">

1111 1111 255.

Line 361 ⟶ 363:

1010 0001 (two's complement) 161.

</pre>

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

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

!Two's complement

!Decimal

|-

|align="center"| 0111 ||alignstyle="text-align:right"| 7. 

|-

|align="center"| 0110 ||alignstyle="text-align:right"| 6. 

|-

|align="center"| 0101 ||alignstyle="text-align:right"| 5. 

|-

|align="center"| 0100 ||alignstyle="text-align:right"| 4. 

|-

|align="center"| 0011 ||alignstyle="text-align:right"| 3. 

|-

|align="center"| 0010 ||alignstyle="text-align:right"| 2. 

|-

|align="center"| 0001 ||alignstyle="text-align:right"| 1. 

|-

|align="center"| 0000 ||alignstyle="text-align:right"| 0. 

|-

|align="center"| 1111 ||alignstyle="text-align:right"| −1. 

|-

|align="center"| 1110 ||alignstyle="text-align:right"| −2. 

|-

|align="center"| 1101 ||alignstyle="text-align:right"| −3. 

|-

|align="center"| 1100 ||alignstyle="text-align:right"| −4. 

|-

|align="center"| 1011 ||alignstyle="text-align:right"| −5. 

|-

|align="center"| 1010 ||alignstyle="text-align:right"| −6. 

|-

|align="center"| 1001 ||alignstyle="text-align:right"| −7. 

|-

|align="center"| 1000 ||alignstyle="text-align:right"| −8. 

|}

Fundamentally, the system represents negative integers by counting backward and [[modular arithmetic|wrapping around]]. The boundary between positive and negative numbers is arbitrary, but by [[Convention (norm)|convention]] all negative numbers have a left-most bit ([[most significant bit]]) of one. Therefore, the most positive four-bit number is 0111&nbsp;(7.) and the most negative is 1000 (&minus;8−8.). Because of the use of the left-most bit as the sign bit, the absolute value of the most negative number (|&minus;8−8.| = 8.) is too large to represent. Negating a two's complement number is simple: Invert all the bits and add one to the result. For example, negating 1111, we get {{nowrap|0000 + 1 {{=}} 1}}. Therefore, 1111 in binary must represent &minus;1−1 in decimal.<ref>{{cite web

|first=Thomas |last=Finley

|date=April 2000

|title=Two's Complement

|series=Class notes for CS&nbsp;104

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

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

}}</ref>

The system is useful in simplifying the implementation of arithmetic on computer hardware. Adding 0011&nbsp;(3.) to 1111&nbsp;(&minus;1−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&nbsp;(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 or 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 operates as if there were an extra left-most bit of 1.

Line 415 ⟶ 417:

===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)

Line 434 ⟶ 436:

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

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)

Line 444 ⟶ 446:

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₂ = 10₁₀ is outside the permitted range of &minus;8−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 &minus;16−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&mdash; – which is equivalent to the method of comparing the carry bits&mdash; – but which may be easier to implement in some situations, because it does not require access to the internals of the addition.

===Subtraction===

Line 482 ⟶ 484:

|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 &times;× (&minus;5−5) = &minus;30−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)

Line 500 ⟶ 502:

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 &minus;5−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)

Line 522 ⟶ 524:

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

Line 529 ⟶ 531:

// 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

Line 551 ⟶ 553:

In a 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 two's-complement."<ref>{{cite web |url=http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154 |title=Programming Hacks |work=HAKMEM |at=ITEM 154 (Gosper) |archive-url=https://web.archive.org/web/20240224184437/http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154 |archive-date=2024-02-24 |url-status=dead}}</ref>

Gosper's end conclusion is not necessarily meant to be taken seriously, and it is akin to a [[mathematical joke]]. The critical step is "...110 = ...111&nbsp;−&nbsp;1", i.e., "2''X'' = ''X''&nbsp;−&nbsp;1", and thus ''X''&nbsp;=&nbsp;...111&nbsp;=&nbsp;−1. 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.<!--Does this interpretation take into account a sign bit?--> It is meaningful either as part of a two's-complement notation for all integers, as a typical [[p-adic number|2-adic number]], or even as one of the generalized sums defined for the [[divergent series]] of real numbers [[1 + 2 + 4 + 8 + …|1 + 2 + 4 + 8 + ···⋯]].<ref>For the summation of 1 + 2 + 4 + 8 + ···⋯ without recourse to the 2-adic metric, see {{cite book |last=Hardy |first=G. H. |author-link=G. H. Hardy |title=Divergent Series |year=1949 |publisher=Clarendon Press |id={{LCC|QA295|.H29|1967}} |pages=7–10}} (pp. 7–10)</ref> 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.<ref>{{cite book |title=On circuits and numbers |last=Vuillemin |first=Jean |year=1993 |publisher=[[Digital Equipment Corp.Corporation]] |___location=Paris |page=19 |url=https://hplabs.itcs.hp.com/techreports/Compaq-DEC/PRL-RR-25.pdf |access-date=2023-03-29}}, |chapter=Chapter 7,}} See especially chapter 7.3 for multiplication.</ref> [[continuous function|Continuity]] of binary arithmetical and [[bitwise operation]]s in 2-adic [[metric space|metric]] also has some use in cryptography.<ref>{{cite web |url=http://crypto.rsuh.ru/ |title=ABC Stream Cipher |last1=Anashin|first1=Vladimir |last2=Bogdanov|first2=Andrey |last3=Kizhvatov|first3=Ilya |year=2007 |publisher=[[Russian State University for the Humanities]] |access-date=24 January 2012}}</ref>

== Fraction conversion ==

Line 573 ⟶ 575:

==Further reading==

* [https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html Two's Complement Explanation,] (Thomas Finley, 2000)]

*{{cite book |first=Israel |last=Koren |title=Computer Arithmetic Algorithms |publisher=A. K. Peters |year=2002 |isbn=1-56881-160-8 }}

*{{cite book |first=Ivan |last=Flores |title=The Logic of Computer Arithmetic |publisher=Prentice-Hall |year=1963 }}