Signed number representations: Difference between revisions

Revision as of 04:20, 13 July 2019

Latest revision as of 19:13, 19 August 2025

(118 intermediate revisions by 49 users not shown)

Line 1:

{{Short description|Encoding of negative numbers in binary number systems}}

{{Refimprove|date=April 2013}}

{{distinguish|Signed-digit representation}}

In [[computing]], '''signed number representations''' are required to encode [[negative number]]s in binary number systems.

In [[mathematics]], negative numbers in any base are represented by prefixing them with a minus sign ("−−") sign. However, in [[computerRAM]] hardwareor CPU [[Processor register|registers]], numbers are represented only as sequences of [[bit]]s, without extra symbols. The four best-known methods of extending the [[binary numeral system]] to represent [[signed number]]s are: [[#Sign-and-magnitude methodSign–magnitude|sign-and-magnitudesign–magnitude]], [[#Ones' complement|ones' complement]], [[#Two's complement|two's complement]], and [[#Excess-K|offset binary]]. Some of the alternative methods use implicit instead of explicit signs, such as negative binary, using the [[#Base −2|base −2]]. Corresponding methods can be devised for [[positional notation|other bases]], whether positive, negative, fractional, or other elaborations on such themes.

There is no definitive criterion by which any of the representations is universally superior. TheFor integers, the representation used in most current computing devices is two's complement, although the [[UNIVAC 1100/2200 series|Unisys ClearPath Dorado series]] mainframes use ones' complement.

<!-- Note: "For integers" to exclude the significand and the exponent field of IEEE 754 floating-point numbers. -->

== History ==

The early days of digital computing were marked by a lot of competing ideas about both hardware technology and mathematics technology (numbering systems). One of the great debates was the format of negative numbers, with some of the era's most expert people having very strong and different opinions.{{Citation needed|reason=Please reference these debates|date=May 2012}} One camp supported [[two's complement]], the system that is dominant today. Another camp supported ones' complement, where any positive value is made into its negative equivalent by inverting all of the bits in a word. A third group supported "sign &amp; magnitude" (sign-magnitude), where a value is changed from positive to negative simply by toggling the word's sign (high-order) bit.

The early days of digital computing were marked by competing ideas about both hardware technology and mathematics technology (numbering systems). One of the great debates was the format of negative numbers, with some of the era's top experts expressing very strong and differing opinions.{{Citation needed|reason=Please reference these debates|date=May 2012}} One camp supported [[two's complement]], the system that is dominant today. Another camp supported ones' complement, where a negative value is formed by inverting all of the bits in its positive equivalent. A third group supported sign–magnitude, where a value is changed from positive to negative simply by toggling the word's highest-order bit.

There were arguments for and against each of the systems.<!--{{Citation needed|reason=Cite these arguments|date=May 2012}}--the rest of the article gives reasons --> Sign &amp; magnitude allowed for easier tracing of memory dumps (a common process 40 years ago) as small numeric values use fewer 1 bits.<!-- this is obvious enough --> Internally, these systems did ones' complement math so numbers would have to be converted to ones' complement values when they were transmitted from a register to the math unit and then converted back to sign-magnitude when the result was transmitted back to the register<!--{{Citation needed|reason=Cite one of these systems|date=May 2012}}-- this is the most hardware efficient way to do it. It is likely how they did it-->. The electronics required more gates than the other systems{{snd}}a key concern when the cost and packaging of discrete transistors was critical. IBM was one of the early supporters of sign-magnitude, with their [[IBM 704|704]], [[IBM 709|709]] and [[IBM 7090|709x]] series computers being perhaps the best known systems to use it.

There were arguments for and against each of the systems.<!--{{Citation needed|reason=Cite these arguments|date=May 2012}}--the rest of the article gives reasons --> Sign–magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 bits.<!-- this is obvious enough --> These systems did ones' complement math internally, so numbers would have to be converted to ones' complement values when they were transmitted from a register to the math unit and then converted back to sign–magnitude when the result was transmitted back to the register<!--{{Citation needed|reason=Cite one of these systems|date=May 2012}}-- this is the most hardware efficient way to do it. It is likely how they did it-->. The electronics required more gates than the other systems{{snd}}a key concern when the cost and packaging of discrete transistors were critical. IBM was one of the early supporters of sign–magnitude, with their [[IBM 704|704]], [[IBM 709|709]] and [[IBM 7090|709x]] series computers being perhaps the best-known systems to use it.

Ones' complement allowed for somewhat simpler hardware designs as there was no need to convert values when passed to and from the math unit. But it also shared an undesirable characteristic with sign-magnitude{{snd}}the ability to represent [[negative zero]] (−0). Negative zero behaves exactly like positive zero; when used as an operand in any calculation, the result will be the same whether an operand is positive or negative zero. The disadvantage, however, is that the existence of two forms of the same value necessitates two rather than a single comparison when checking for equality with zero. Ones' complement subtraction can also result in an [[end-around borrow]] (described below). It can be argued that this makes the addition/subtraction logic more complicated or that it makes it simpler as a subtraction requires simply inverting the bits of the second operand as it is passed to the adder. The [[PDP-1]], [[CDC 160 series]], [[CDC 3000]] series, [[CDC 6000 series]], [[UNIVAC 1100]] series, and the [[LINC]] computer use ones' complement representation.

Ones' complement allowed for somewhat simpler hardware designs, as there was no need to convert values when passed to and from the math unit. But it also shared an undesirable characteristic with sign–magnitude: the ability to represent [[negative zero]] (−0). Negative zero behaves exactly like positive zero: when used as an operand in any calculation, the result will be the same whether an operand is positive or negative zero. The disadvantage is that the existence of two forms of the same value necessitates two comparisons when checking for equality with zero. Ones' complement subtraction can also result in an [[end-around borrow]] (described below). It can be argued that this makes the addition and subtraction logic more complicated or that it makes it simpler, as a subtraction requires simply inverting the bits of the second operand as it is passed to the adder. The [[PDP-1]], [[CDC 160 series]], [[CDC 3000]] series, [[CDC 6000 series]], [[UNIVAC 1100]] series, and [[LINC]] computer use ones' complement representation.

Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity.{{Citation needed|reason=Has it ever been proven to be the easiest to implement|date=May 2012}} Processors on the early mainframes often consisted of thousands of transistors{{snd}}eliminating a significant number of transistors was a significant cost savings. Mainframes such as the [[IBM System/360]], the [[GE-600 series]],<ref>{{cite book|url=http://ed-thelen.org/comp-hist/GE-635.html#Binary%20Fixed-Point%20Numbers|title=GE-625 / 635 Programming Reference Manual|publisher=[[General Electric]]|date=January 1966|accessdate=August 15, 2013}}</ref> and the [[PDP-6]] and [[PDP-10]] use two's complement, as did minicomputers such as the [[PDP-5]] and [[PDP-8]] and the [[PDP-11]] and [[VAX]]. The architects of the early integrated circuit-based CPUs ([[Intel 8080]], etc.) chose to use two's complement math. As IC technology advanced, virtually all adopted two's complement technology. [[x86]],<ref>{{cite book|url=http://download.intel.com/products/processor/manual/325462.pdf|title=Intel 64 and IA-32 Architectures Software Developer’s Manual|at=Section 4.2.1|publisher=[[Intel]]|accessdate=August 6, 2013}}</ref> [[m68k]], [[Power ISA]],<ref>{{cite book|url=https://www.power.org/documentation/power-isa-version-2-07/|title=Power ISA Version 2.07|at=Section 1.4|publisher=[[Power.org]]|accessdate=August 6, 2013}},</ref> [[MIPS architecture|MIPS]], [[SPARC]], [[ARM architecture|ARM]], [[Itanium]], [[PA-RISC]], and [[DEC Alpha]] processors are all two's complement.

Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity.<ref>{{cite journal|title=Two's complement computation sharing multiplier and its applications to high performance DFE|first1=Hunsoo|last1=Choo|first2=K.|last2=Muhammad|first3=K.|last3=Roy|journal=IEEE Transactions on Signal Processing|volume=51|issue=2|date=February 2003|pages=458–469|doi=10.1109/TSP.2002.806984|bibcode=2003ITSP...51..458C |url=https://www.academia.edu/29135370}}</ref> Processors on the early mainframes often consisted of thousands of transistors, so eliminating a significant number of transistors was a significant cost savings. Mainframes such as the [[IBM System/360]], the [[GE-600 series]],<ref>{{cite book|url=http://ed-thelen.org/comp-hist/GE-635.html#Binary%20Fixed-Point%20Numbers|title=GE-625 / 635 Programming Reference Manual|publisher=[[General Electric]]|date=January 1966|access-date=August 15, 2013}}</ref> and the [[PDP-6]] and [[PDP-10]] use two's complement, as did minicomputers such as the [[PDP-5]] and [[PDP-8]] and the [[PDP-11]] and [[VAX]] machines. The architects of the early integrated-circuit-based CPUs ([[Intel 8080]], etc.) also chose to use two's complement math. As IC technology advanced, two's complement technology was adopted in virtually all processors, including [[x86]],<ref>{{cite book|url=http://download.intel.com/products/processor/manual/325462.pdf|title=Intel 64 and IA-32 Architectures Software Developer's Manual|at=Section 4.2.1|publisher=[[Intel]]|access-date=August 6, 2013}}</ref> [[m68k]], [[Power ISA]],<ref>{{cite book|url=https://fileadmin.cs.lth.se/cs/education/EDAN25/PowerISA_V2.07_PUBLIC.pdf|title=Power ISA Version 2.07|at=Section 1.4|publisher=[[Power.org]]|access-date=November 2, 2023}},</ref> [[MIPS architecture|MIPS]], [[SPARC]], [[ARM architecture|ARM]], [[Itanium]], [[PA-RISC]], and [[DEC Alpha]].

=={{anchor|Sign-and-magnitude method}}Signed magnitude representation (SMR)==

This representation is also called "sign–magnitude" or "sign and magnitude" representation. In this approach, a number's sign is represented with a '''[[sign bit]]''': setting that [[bit]] (often the [[most significant bit]]) to 0 for a positive number or positive zero, and setting it to 1 for a negative number or negative zero. The remaining bits in the number indicate the magnitude (or [[absolute value]]). For example, in an eight-bit [[byte]], only seven bits represent the magnitude, which can can range from 0000000 (0) to 1111111 (127). Thus numbers ranging from &minus;127₁₀ to +127₁₀ can be represented once the sign bit (the eighth bit) is added. For example, &minus;43₁₀ encoded in an eight-bit byte is <strong>1</strong>0101011 while 43₁₀ is <strong>0</strong>0101011. A consequence of using signed magnitude representation is that there are two ways to represent zero, 00000000 (0) and 10000000 ([[−0]]).

== Sign–magnitude ==

This approach is directly comparable to the common way of showing a sign (placing a "+" or "&minus;" next to the number's magnitude). Some early binary computers (e.g., [[IBM 7090]]) use this representation, perhaps because of its natural relation to common usage. Signed magnitude is the most common way of representing the [[significand]] in [[floating point]] values.

{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center"

|+ Eight-bit sign–magnitude

|-

! Binary value

! Sign–magnitude interpretation

! Unsigned interpretation

|-

| 00000000 || 0 || 0

|-

| 00000001 || 1 || 1

|-

| ⋮ || ⋮ || ⋮

|-

| 01111101 || 125 || 125

|-

| 01111110 || 126 || 126

|-

| 01111111 || 127 || 127

|-

| 10000000 || −0 || 128

|-

| 10000001 || −1 || 129

|-

| 10000010 || −2 || 130

|-

| ⋮ || ⋮ || ⋮

|-

| 11111101 || −125 || 253

|-

| 11111110 || −126 || 254

|-

| 11111111 || −127 || 255

|}

In the '''sign–magnitude''' representation, also called '''sign-and-magnitude''' or '''signed magnitude''', a signed number is represented by the bit pattern corresponding to the sign of the number for the [[sign bit]] (often the [[most significant bit]], set to 0 for a positive number and to 1 for a negative number), and the magnitude of the number (or [[absolute value]]) for the remaining bits. For example, in an eight-bit [[byte]], only seven bits represent the magnitude, which can range from 0000000 (0) to 1111111 (127). Thus numbers ranging from −127₁₀ to +127₁₀ can be represented once the sign bit (the eighth bit) is added. For example, −43₁₀ encoded in an eight-bit byte is '''1'''0101011 while 43₁₀ is '''0'''0101011. Using sign–magnitude representation has multiple consequences which makes them more intricate to implement:<ref name="cs315">{{cite web |last1=Bacon |first1=Jason W. |url=http://www.cs.uwm.edu/classes/cs315/Bacon/Lecture/HTML/ch04s11.html |title=Computer Science 315 Lecture Notes |access-date=21 February 2020 |date=2010–2011 |archive-date=14 February 2020 |archive-url=https://web.archive.org/web/20200214050150/http://www.cs.uwm.edu/classes/cs315/Bacon/Lecture/HTML/ch04s11.html |url-status=dead }}</ref>

# There are two ways to represent zero, 00000000 (0) and 10000000 ([[−0]]).

# Addition and subtraction require different behavior depending on the sign bit, whereas ones' complement can ignore the sign bit and just do an end-around carry, and two's complement can ignore the sign bit and depend on the overflow behavior.

# Comparison also requires inspecting the sign bit, whereas in two's complement, one can simply subtract the two numbers, and check if the outcome is positive or negative.

# The minimum negative number is −127, instead of −128 as in the case of two's complement.

This approach is directly comparable to the common way of showing a sign (placing a "+" or "−" next to the number's magnitude). Some early binary computers (e.g., [[IBM 7090]]) use this representation, perhaps because of its natural relation to common usage. Sign–magnitude is the most common way of representing the [[significand]] in [[Floating-point arithmetic|floating-point]] values.

== Ones' complement ==

{{Main|Ones' complement}}

==Ones' complement==

{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center"

|+ Eight-bit ones' complement

Line 29 ⟶ 75:

! Unsigned interpretation

|-

| 00000000 || +0 || 0

|-

| 00000001 || 1 || 1

|-

| ⋮ || ⋮ || ⋮

|-

| 01111101 || 125 || 125

|-

| 01111110 || 126 || 126

|-

| 01111111 || 127 || 127

|-

| 10000000 || −127 || 128

Line 47 ⟶ 93:

| 10000010 || −125 || 130

|-

| ⋮ || ⋮ || ⋮

|-

| 11111101 || −2 || 253

|-

| 11111110 || −1 || 254

|-

| 11111111 || −0 || 255

|}

In the ''ones' complement'' representation,<ref>{{Cite patent|title=Array multiplier operating in one's complement format|gdate=1981-03-10|country=US|number=4484301|url=https://patents.google.com/patent/US4484301A/en}}</ref> a negative number is represented by the bit pattern corresponding to the [[bitwise NOT]] (i.e. the "complement") of the positive number. Like sign–magnitude representation, ones' complement has two representations of 0: 00000000 (+0) and 11111111 ([[−0]]).<ref>{{Cite patent|title=One's complement cryptographic combiner|gdate=1999-12-11|country=US|number=6760440|url=https://patents.google.com/patent/US6760440B1/en}}</ref>

{{Main|Ones' complement}}

As an example, the ones' complement form of 00101011 (43₁₀) becomes 11010100 (−43₁₀). The range of [[signedness|signed]] numbers using ones' complement is represented by {{nobr|−(2^''N''−1 − 1)}} to {{nobr|(2^''N''−1 − 1)}} and ±0. A conventional eight-bit byte is −127₁₀ to +127₁₀ with zero being either 00000000 (+0) or 11111111 (−0).

Alternatively, a system known as ones' complement can be used to represent negative numbers. The ones' complement form of a negative binary number is the [[bitwise NOT]] applied to it, i.e. the "complement" of its positive counterpart. Like sign-and-magnitude representation, ones' complement has two representations of 0: 00000000 (+0) and 11111111 ([[−0]]).

To add two numbers represented in this system, one does a conventional binary addition, but it is then necessary to do an ''end-around carry'': that is, add any resulting [[carry flag|carry]] back into the resulting sum.<ref>{{cite journal |last1=Shedletsky |first1=John J. |title=Comment on the Sequential and Indeterminate Behavior of an End-Around-Carry Adder |journal=IEEE Transactions on Computers |date=1977 |volume=26 |issue=3 |pages=271–272 |doi=10.1109/TC.1977.1674817|s2cid=14661474 }}</ref> To see why this is necessary, consider the following example showing the case of the addition of −1 (11111110) to [phone]):

As an example, the ones' complement form of 00101011 (43₁₀) becomes 11010100 (&minus;43₁₀). The range of [[signedness|signed]] numbers using ones' complement is represented by {{nobr|−(2^''N''−1 − 1)}} to {{nobr|(2^''N''−1 − 1)}} and ±0. A conventional eight-bit byte is −127₁₀ to +127₁₀ with zero being either 00000000 (+0) or 11111111 (−0).

<pre>

To add two numbers represented in this system, one does a conventional binary addition, but it is then necessary to do an ''end-around carry'': that is, add any resulting [[carry flag|carry]] back into the resulting sum. To see why this is necessary, consider the following example showing the case of the addition of &minus;1 (11111110) to [phone]):

binary decimal

11111110 −1

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

+ 00000010 +2

binary decimal

─────────── ──

11111110 –1

1 00000000 + 000000100 ← Incorrect +2answer

1 +1 ← Add carry
─────────── ──

00000001 1 00000000 01 ← Not the correctCorrect answer

1 +1 ← Add carry

─────────── ──

00000001 1 ← Correct answer

</pre>

Line 79 ⟶ 123:

A remark on terminology: The system is referred to as "ones' complement" because the [[Negation#Programming|negation]] of a positive value <var>x</var> (represented as the [[bitwise NOT]] of <var>x</var>) can also be formed by subtracting <var>x</var> from the ones' complement representation of zero that is a long sequence of ones (−0). Two's complement arithmetic, on the other hand, forms the negation of <var>x</var> by subtracting <var>x</var> from a single large power of two that is [[Congruence relation|congruent]] to +0.<ref>Donald Knuth: ''[[The Art of Computer Programming]]'', Volume 2: Seminumerical Algorithms, chapter 4.1</ref> Therefore, ones' complement and two's complement representations of the same negative value will differ by one.

Note that the ones' complement representation of a negative number can be obtained from the sign-magnitudesign–magnitude representation merely by [[bitwise complement|bitwise complementing]] the magnitude (inverting all the bits after the first). For example, the decimal number −125 with its sign–magnitude representation 11111101 can be represented in ones' complement form as 10000010.

== Two's complement ==

{{Main|Two's complement}}

==Two's complement==

{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center"

|+ Eight-bit two's complement

Line 89 ⟶ 135:

! Unsigned interpretation

|-

| 00000000 || 0 || 0

|-

| 00000001 || 1 || 1

|-

| ⋮ || ⋮ || ⋮

|-

| 01111110 || 126 || 126

|-

| 01111111 || 127 || 127

|-

| 10000000 || −128 || 128

Line 105 ⟶ 151:

| 10000010 || −126 || 130

|-

| ⋮ || ⋮ || ⋮

|-

| 11111110 || −2 || 254

|-

| 11111111 || −1 || 255

|}

In the ''two's complement'' representation, a negative number is represented by the bit pattern corresponding to the [[bitwise NOT]] (i.e. the "complement") of the positive number plus one, i.e. to the ones' complement plus one. It circumvents the problems of multiple representations of 0 and the need for the [[end-around carry]] of the ones' complement representation. This can also be thought of as the most significant bit representing the inverse of its value in an unsigned integer; in an 8-bit unsigned byte, the most significant bit represents the 128ths place, where in two's complement that bit would represent −128.

{{Main|Two's complement}}

The problems of multiple representations of 0 and the need for the [[end-around carry]] are circumvented by a system called '''two's complement'''. In two's complement, negative numbers are represented by the bit pattern which is one greater (in an unsigned sense) than the ones' complement of the positive value.

In two's-complement, there is only one zero, represented as 00000000. Negating a number (whether negative or positive) is done by inverting all the bits and then adding one to that result.<ref>{{cite web|title=Two's Complement|url=httphttps://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html|publisher=[[Cornell University]]|date=April 2000|author=Thomas Finley|accessdateaccess-date=15 September 2015}}</ref> This actually reflects the [[ring (mathematics)|ring]] structure on all integers [[modular arithmetic|modulo]] [[power of two|2^''N'']]: <math>\mathbb{Z}/2^N\mathbb{Z}</math>. Addition of a pair of two's-complement integers is the same as addition of a pair of [[signedness|unsigned numbers]] (except for detection of [[integer overflow|overflow]], if that is done); the same is true for subtraction and even for ''N'' lowest significant bits of a product (value of multiplication). For instance, a two's-complement addition of 127 and −128 gives the same binary bit pattern as an unsigned addition of 127 and 128, as can be seen from the 8-bit two's complement table.

An easier method to get the negation of a number in two's complement is as follows:

Line 136 ⟶ 180:

Method two:

# Invert all the bits through the number. This computes the same result as subtracting from negative one.

# Add one

Line 146 ⟶ 190:

{{clear}}

== {{anchor|Excess-128|Excess-K}}Offset binary ==

{{Main|Offset binary}}

{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center"

|+ Eight-bit excess-128

Line 154 ⟶ 200:

!Unsigned interpretation

|-

| 00000000 || −128 || 0

|-

| 00000001 || −127 || 1

|-

| ⋮ || ⋮ || ⋮

|-

| 01111111 || −1 || 127

|-

| 10000000 || 0 || 128

|-

| 10000001 || 1 || 129

|-

| ⋮ || ⋮ || ⋮

|-

| 11111111 || +127 || 255

|-

|}

In the ''offset binary'' representation, also called ''excess-<var>K</var>'' or ''biased'', a signed number is represented by the bit pattern corresponding to the unsigned number plus <var>K</var>, with <var>K</var> being the ''biasing value'' or ''offset''. Thus 0 is represented by <var>K</var>, and −<var>K</var> is represented by an all-zero bit pattern. This can be seen as a slight modification and generalization of the aforementioned two's-complement, which is virtually the {{nobr|excess-(2^{<var>N</var>−1})}} representation with [[negated]] [[most significant bit]].

{{Main|Offset binary}}

Biased representations are now primarily used for the exponent of [[floating-point]] numbers. The [[IEEE 754|IEEE 754 floating-point standard]] defines the exponent field of a [[single-precision]] (32-bit) number as an 8-bit [[excess-127]] field. The [[double-precision]] (64-bit) exponent field is an 11-bit [[excess-1023]] field; see [[exponent bias]]. It also had use for binary-coded decimal numbers as [[excess-3]].

[[Offset binary]], also called [[Excess-K|excess-<var>K</var>]] or [[biased representation (arithmetics)|biased representation]], uses a pre-specified number <var>K</var> as a biasing value. A value is represented by the unsigned number which is <var>K</var> greater than the intended value. Thus 0 is represented by <var>K</var>, and &minus;<var>K</var> is represented by the all-zeros bit pattern. This can be seen as a slight modification and generalization of the aforementioned two's-complement, which is virtually the {{nobr|excess-(2^{<var>N</var>−1})}} representation with [[negated]] [[most significant bit]].

== Base −2 ==

Biased representations are now primarily used for the exponent of [[floating-point]] numbers. The [[IEEE floating-point standard]] defines the exponent field of a [[single-precision]] (32-bit) number as an 8-bit [[excess-127]] field. The [[double-precision]] (64-bit) exponent field is an 11-bit [[excess-1023]] field; see [[exponent bias]]. It also had use for binary-coded decimal numbers as [[excess-3]].

==Base −2==

{{See also|Negative base}}

In conventional binary number systems, the base, or [[radix]], is 2; thus the rightmost bit represents 2⁰, the next bit represents 2¹, the next bit 2², and so on. However, a binary number system with base &minus;2 is also possible.

{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center"

The rightmost bit represents {{nowrap|(&minus;2)⁰ {{=}} +1}}, the next bit represents {{nowrap|(&minus;2)¹ {{=}} &minus;2}}, the next bit {{nowrap|(&minus;2)² {{=}} +4}} and so on, with alternating sign. The numbers that can be represented with four bits are shown in the comparison table below.

|+ Eight-bit base −2

|-

!Binary value

!Base −2 interpretation

!Unsigned interpretation

|-

| 00000000 || 0 || 0

|-

| 00000001 || 1 || 1

|-

| ⋮ || ⋮ || ⋮

|-

| 01111111 || 43 || 127

|-

| 10000000 || −128 || 128

|-

| 10000001 || −127 || 129

|-

| ⋮ || ⋮ || ⋮

|-

| 11111111 || −85 || 255

|-

|}

In the ''base −2'' representation, a signed number is represented using a number system with base −2. In conventional binary number systems, the base, or [[radix]], is 2; thus the rightmost bit represents 2⁰, the next bit represents 2¹, the next bit 2², and so on. However, a binary number system with base −2 is also possible. The rightmost bit represents {{nowrap|(−2)⁰ {{=}} +1}}, the next bit represents {{nowrap|(−2)¹ {{=}} −2}}, the next bit {{nowrap|(−2)² {{=}} +4}} and so on, with alternating sign. The numbers that can be represented with four bits are shown in the comparison table below.

The range of numbers that can be represented is asymmetric. If the word has an even number of bits, the magnitude of the largest negative number that can be represented is twice as large as the largest positive number that can be represented, and vice versa if the word has an odd number of bits.

== Comparison table ==

The following table shows the positive and negative integers that can be represented using four bits.

Line 193 ⟶ 263:

! style="width: 7em" | Decimal

! style="width: 7em" | Unsigned

! style="width: 7em" | Sign and magnitudeSign–magnitude

! style="width: 7em" | Ones' complement

! style="width: 7em" | Two's complement

! style="width: 7em" | Excess-8 (biased)

! style="width: 7em" | Base −2

|-

| align=right|+16&nbsp;&nbsp;&nbsp;&nbsp;

| {{n/a}}

| {{n/a}}

Line 207 ⟶ 277:

| {{n/a}}

|-

| align=right|+15&nbsp;&nbsp;&nbsp;&nbsp;

| 1111

| {{n/a}}

Line 215 ⟶ 285:

| {{n/a}}

|-

| align=right|+14&nbsp;&nbsp;&nbsp;&nbsp;

| 1110

| {{n/a}}

Line 223 ⟶ 293:

| {{n/a}}

|-

| align=right|+13&nbsp;&nbsp;&nbsp;&nbsp;

| 1101

| {{n/a}}

Line 231 ⟶ 301:

| {{n/a}}

|-

| align=right|+12&nbsp;&nbsp;&nbsp;&nbsp;

| 1100

| {{n/a}}

Line 239 ⟶ 309:

| {{n/a}}

|-

| align=right|+11&nbsp;&nbsp;&nbsp;&nbsp;

| 1011

| {{n/a}}

Line 247 ⟶ 317:

| {{n/a}}

|-

| align=right|+10&nbsp;&nbsp;&nbsp;&nbsp;

| 1010

| {{n/a}}

Line 255 ⟶ 325:

| {{n/a}}

|-

| align=right|+9&nbsp;&nbsp;&nbsp;&nbsp;

| 1001

| {{n/a}}

Line 263 ⟶ 333:

| {{n/a}}

|-

| align=right|+8&nbsp;&nbsp;&nbsp;&nbsp;

| 1000

| {{n/a}}

Line 271 ⟶ 341:

| {{n/a}}

|-

| align=right|+7&nbsp;&nbsp;&nbsp;&nbsp;

| 0111

| 0111

Line 279 ⟶ 349:

| {{n/a}}

|-

| align=right|+6&nbsp;&nbsp;&nbsp;&nbsp;

| 0110

| 0110

Line 287 ⟶ 357:

| {{n/a}}

|-

| align=right|+5&nbsp;&nbsp;&nbsp;&nbsp;

| 0101

| 0101

Line 295 ⟶ 365:

| 0101

|-

| align=right|+4&nbsp;&nbsp;&nbsp;&nbsp;

| 0100

| 0100

Line 303 ⟶ 373:

| 0100

|-

| align=right|+3&nbsp;&nbsp;&nbsp;&nbsp;

| 0011

| 0011

Line 311 ⟶ 381:

| 0111

|-

| align=right|+2&nbsp;&nbsp;&nbsp;&nbsp;

| 0010

| 0010

Line 319 ⟶ 389:

| 0110

|-

| align=right|+1&nbsp;&nbsp;&nbsp;&nbsp;

| 0001

| 0001

Line 327 ⟶ 397:

| 0001

|-

| align=right|+0&nbsp;&nbsp;&nbsp;&nbsp;

| rowspan=2 valign=center |0000

| 0000

Line 427 ⟶ 497:

| {{n/a}}

|}

Same table, as viewed from "given these binary bits, what is the number as interpreted by the representation system":

Line 433 ⟶ 502:

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

|-

! Binary !! Unsigned !! Sign and magnitudeSign–magnitude !! Ones' complement !! Two's complement !! Excess-8 !! Base −2

|-

| 0000 || 0 || 0 || 0 || 0 || −8 || 0

|-

| 0001 || 1 || 1 || 1 || 1 || −7 || 1

|-

| 0010 || 2 || 2 || 2 || 2 || −6 || −2

|-

| 0011 || 3 || 3 || 3 || 3 || −5 || −1

|-

| 0100 || 4 || 4 || 4 || 4 || −4 || 4

|-

| 0101 || 5 || 5 || 5 || 5 || −3 || 5

|-

| 0110 || 6 || 6 || 6 || 6 || −2 || 2

|-

| 0111 || 7 || 7 || 7 || 7 || −1 || 3

|-

| 1000 || 8 || [[Signed zero|−0]] || −7 || −8 || 0 || −8

|-

| 1001 || 9 || −1 || −6 || −7 || 1 || −7

|-

| 1010 || 10 || −2 || −5 || −6 || 2 || −10

|-

| 1011 || 11 || −3 || −4 || −5 || 3 || −9

|-

| 1100 || 12 || −4 || −3 || −4 || 4 || −4

|-

| 1101 || 13 || −5 || −2 || −3 || 5 || −3

|-

| 1110 || 14 || −6 || −1 || −2 || 6 || −6

|-

| 1111 || 15 || −7 || [[Signed zero|−0]] || −1 || 7 || −5

|}

== Other systems ==

Google's [[Protocol Buffers]] "zig-zag encoding" is a system similar to sign-and-magnitude, but uses the [[least significant bit]] to represent the sign and has a single representation of zero. This allows a [[variable-length quantity]] encoding intended for nonnegative (unsigned) integers to be used efficiently for signed integers.<ref>[http://developers.google.com/protocol-buffers/docs/encoding#types Protocol Buffers: Signed Integers]</ref>

Google's [[Protocol Buffers]] "zig-zag encoding" is a system similar to sign–magnitude, but uses the [[least significant bit]] to represent the sign and has a single representation of zero. This allows a [[variable-length quantity]] encoding intended for nonnegative (unsigned) integers to be used efficiently for signed integers.<ref>[http://developers.google.com/protocol-buffers/docs/encoding#types Protocol Buffers: Signed Integers]</ref>

A similar method is used in the [[Advanced Video Coding|Advanced Video Coding/H.264]] and [[High Efficiency Video Coding|High Efficiency Video Coding/H.265]] video compression standards to [[Exponential-Golomb coding#Extension to negative numbers|extend exponential-Golomb coding]] to negative numbers. In that extension, the [[least significant bit]] is almost a sign bit; zero has the same least significant bit (0) as all the negative numbers. This choice results in the largest magnitude representable positive number being one higher than the largest magnitude negative number, unlike in two's complement or the Protocol Buffers zig-zag encoding.

Another approach is to give each [[numerical digit|digit]] a sign, yielding the [[signed-digit representation]]. For instance, in 1726, [[John Colson]] advocated reducing expressions to "small numbers", numerals 1, 2, 3, 4, and 5. In 1840, [[Augustin Cauchy]] also expressed preference for such modified decimal numbers to reduce errors in computation.

== See also ==

{{Portal|Computer science}}

* [[Balanced ternary]]

* [[Binary-coded decimal]]

* [[Computer numberingnumber formatsformat]]

* [[Method of complements]]

* [[Signedness]]

== References ==

{{reflist}}

{{Reflist}}

* Ivan Flores, ''The Logic of Computer Arithmetic'', Prentice-Hall (1963)

* Israel Koren, ''Computer Arithmetic Algorithms'', A.K. Peters (2002), {{ISBN|1-56881-160-8}}

Line 493 ⟶ 565:

[[cs:Dvojková soustava#Zobrazení záporných čísel]]

[[fr:Système binaire#Représentation des entiers négatifs]]

[[vi:Biểu diễn số âm]]