Signed number representations

Not to be confused withSigned-digit representation.

Incomputing,signed number representationsare required to encodenegative numbersin binary number systems.

Inmathematics,negative numbers in any base are represented by prefixing them with a minus sign ( "−" ). However, inRAMor CPUregisters,numbers are represented only as sequences ofbits,without extra symbols. The four best-known methods of extending thebinary numeral systemto representsigned numbersare:sign–magnitude,ones' complement,two's complement,andoffset binary.Some of the alternative methods use implicit instead of explicit signs, such as negative binary, using thebase −2.Corresponding methods can be devised forother 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. For integers, the representation used in most current computing devices is two's complement, although theUnisys ClearPath Dorado seriesmainframes use ones' complement.

History

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.One camp supportedtwo'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. Sign–magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 bits. 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. The electronics required more gates than the other systems – a key concern when the cost and packaging of discrete transistors were critical. IBM was one of the early supporters of sign–magnitude, with their704,709and709xseries 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: the ability to representnegative 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 anend-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. ThePDP-1,CDC 160 series,CDC 3000series,CDC 6000 series,UNIVAC 1100series, andLINCcomputer use ones' complement representation.

Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity.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 theIBM System/360,theGE-600 series,and thePDP-6andPDP-10use two's complement, as did minicomputers such as thePDP-5andPDP-8and thePDP-11andVAXmachines. 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, includingx86,m68k,Power ISA,MIPS,SPARC,ARM,Itanium,PA-RISC,andDEC Alpha.

Sign–magnitude

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 thesign–magnituderepresentation, also calledsign-and-magnitudeorsigned magnitude,a signed number is represented by the bit pattern corresponding to the sign of the number for thesign bit(often themost significant bit,set to 0 for a positive number and to 1 for a negative number), and the magnitude of the number (orabsolute value) for the remaining bits. For example, in an eight-bitbyte,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 is10101011 while 43₁₀is00101011. Using sign–magnitude representation has multiple consequences which makes them more intricate to implement:

1. There are two ways to represent zero, 00000000 (0) and 10000000 (−0).
2. 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.
3. 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.
4. 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 thesignificandinfloating-pointvalues.

Ones' complement

Main article:Ones' complement

Eight-bit ones' complement

Binary value	Ones' complement interpretation	Unsigned interpretation
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111101	125	125
01111110	126	126
01111111	127	127
10000000	−127	128
10000001	−126	129
10000010	−125	130
⋮	⋮	⋮
11111101	−2	253
11111110	−1	254
11111111	−0	255

In theones' complementrepresentation,a negative number is represented by the bit pattern corresponding to thebitwise 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).

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

To add two numbers represented in this system, one does a conventional binary addition, but it is then necessary to do anend-around carry:that is, add any resultingcarryback into the resulting sum.To see why this is necessary, consider the following example showing the case of the addition of −1 (11111110) to +2 (00000010):

binary decimal
11111110 −1
+ 00000010 +2
─────────── ──
1 00000000 0 ← Not the correct answer
1 +1 ← Add carry
─────────── ──
00000001 1 ← Correct answer

In the previous example, the first binary addition gives 00000000, which is incorrect. The correct result (00000001) only appears when the carry is added back in.

A remark on terminology: The system is referred to as "ones' complement" because thenegationof a positive valuex(represented as thebitwise NOTofx) can also be formed by subtractingxfrom 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 ofxby subtractingxfrom a single large power of two that iscongruentto +0.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–magnitude representation merely bybitwise complementingthe 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 article:Two's complement

Eight-bit two's complement

Binary value	Two's complement interpretation	Unsigned interpretation
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111110	126	126
01111111	127	127
10000000	−128	128
10000001	−127	129
10000010	−126	130
⋮	⋮	⋮
11111110	−2	254
11111111	−1	255

In thetwo's complementrepresentation, a negative number is represented by the bit pattern corresponding to thebitwise 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 theend-around carryof 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.

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.This actually reflects theringstructure on all integersmodulo2^N:$\mathbb {Z} /2^{N}\mathbb {Z}$.Addition of a pair of two's-complement integers is the same as addition of a pair ofunsigned numbers(except for detection ofoverflow,if that is done); the same is true for subtraction and even forNlowest 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:

	Example 1	Example 2
1. Starting from the right, find the first "1"	00101001	00101100
2. Invert all of the bits to the left of that "1"	11010111	11010100

Method two:

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

Example: for +2, which is 00000010 in binary (the ~ character is theCbitwise NOToperator, so ~X means "invert all the bits in X" ):

1. ~00000010 → 11111101
2. 11111101 + 1 → 11111110 (−2 in two's complement)

Offset binary

Main article:Offset binary

Eight-bit excess-128

Binary value	Excess-128 interpretation	Unsigned interpretation
00000000	−128	0
00000001	−127	1
⋮	⋮	⋮
01111111	−1	127
10000000	0	128
10000001	1	129
⋮	⋮	⋮
11111111	127	255

In theoffset binaryrepresentation, also calledexcess-Korbiased,a signed number is represented by the bit pattern corresponding to the unsigned number plusK,withKbeing thebiasing valueoroffset.Thus 0 is represented byK,and −Kis 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 theexcess-(2^N−1)representation withnegatedmost significant bit.

Biased representations are now primarily used for the exponent offloating-pointnumbers. TheIEEE 754 floating-point standarddefines the exponent field of asingle-precision(32-bit) number as an 8-bitexcess-127field. Thedouble-precision(64-bit) exponent field is an 11-bitexcess-1023field; seeexponent bias.It also had use for binary-coded decimal numbers asexcess-3.

Base −2

See also:Negative base

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 thebase −2representation, a signed number is represented using a number system with base −2. In conventional binary number systems, the base, orradix,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(−2)⁰= +1,the next bit represents(−2)¹= −2,the next bit(−2)²= +4and 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.

Four-bit integer representations

Decimal	Unsigned	Sign–magnitude	Ones' complement	Two's complement	Excess-8 (biased)	Base −2
16	—	—	—	—	—	—
15	1111	—	—	—	—	—
14	1110	—	—	—	—	—
13	1101	—	—	—	—	—
12	1100	—	—	—	—	—
11	1011	—	—	—	—	—
10	1010	—	—	—	—	—
9	1001	—	—	—	—	—
8	1000	—	—	—	—	—
7	0111	0111	0111	0111	1111	—
6	0110	0110	0110	0110	1110	—
5	0101	0101	0101	0101	1101	0101
4	0100	0100	0100	0100	1100	0100
3	0011	0011	0011	0011	1011	0111
2	0010	0010	0010	0010	1010	0110
1	0001	0001	0001	0001	1001	0001
0	0000	0000	0000	0000	1000	0000
−0		1000	1111
−1	—	1001	1110	1111	0111	0011
−2	—	1010	1101	1110	0110	0010
−3	—	1011	1100	1101	0101	1101
−4	—	1100	1011	1100	0100	1100
−5	—	1101	1010	1011	0011	1111
−6	—	1110	1001	1010	0010	1110
−7	—	1111	1000	1001	0001	1001
−8	—	—	—	1000	0000	1000
−9	—	—	—	—	—	1011
−10	—	—	—	—	—	1010
−11	—	—	—	—	—	—

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

Binary	Unsigned	Sign–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	−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	−0	−1	7	−5

Other systems

Google'sProtocol Buffers"zig-zag encoding" is a system similar to sign–magnitude, but uses theleast significant bitto represent the sign and has a single representation of zero. This allows avariable-length quantityencoding intended for nonnegative (unsigned) integers to be used efficiently for signed integers.

A similar method is used in theAdvanced Video Coding/H.264andHigh Efficiency Video Coding/H.265video compression standards toextend exponential-Golomb codingto negative numbers. In that extension, theleast significant bitis 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 eachdigita sign, yielding thesigned-digit representation.For instance, in 1726,John Colsonadvocated reducing expressions to "small numbers", numerals 1, 2, 3, 4, and 5. In 1840,Augustin Cauchyalso expressed preference for such modified decimal numbers to reduce errors in computation.

See also

• Balanced ternary
• Binary-coded decimal
• Computer number format
• Method of complements
• Signedness

References

• Ivan Flores,The Logic of Computer Arithmetic,Prentice-Hall (1963)
• Israel Koren,Computer Arithmetic Algorithms,A.K. Peters (2002),ISBN1-56881-160-8