Signed number representations


Signed number representations

In computing, signed number representations are required to encode negative numbers in binary number systems.

In mathematics, negative numbers in any base are represented by prefixing them with a − sign. However, in computer hardware, numbers are represented in binary only without extra symbols, requiring a method of encoding the minus sign. The four best-known methods of extending the binary numeral system to represent signed numbers are: sign-and-magnitude, ones' complement, two's complement, and excess-K. Some of the alternative methods use implicit instead of explicit signs, such as negative binary, using the base −2. Corresponding methods can be devised for other bases, whether positive, negative, fractional, or other elaborations on such themes. In practice the representation most generally used in current computing devices is two's complement, although there is no definitive criterion by which any of the representations is universally superior.

Contents

History

Sign-and-magnitude method

You may first approach the problem of representing a number's sign by allocating one sign bit to represent the sign: set that bit (often the most significant bit) to 0 for a positive number, and set to 1 for a negative number. The remaining bits in the number indicate the magnitude (or absolute value). Hence in a byte with only 7 bits (apart from the sign bit), the magnitude can range from 0000000 (0) to 1111111 (127). Thus you can represent numbers from −12710 to +12710 once you add the sign bit (the eighth bit). A consequence of this representation is that there are two ways to represent zero, 00000000 (0) and 10000000 (−0). Decimal −43 encoded in an eight-bit byte this way is 10101011.

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) used this representation, perhaps because of its natural relation to common usage. Sign-and-magnitude is the most common way of representing the significand in floating point values.

Ones' complement

8 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

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 — the "complement" of its positive counterpart. Like sign-and-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 of signed numbers using ones' complement is represented by −(2N−1−1) to (2N−1−1) and ±0. A conventional eight-bit byte is −12710 to +12710 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 add any resulting carry back 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 binary addition alone gives 00000000, which is incorrect. Only when the carry is added back in does the correct result (00000001) appear.

This numeric representation system was common in older computers; the PDP-1, CDC 160A and UNIVAC 1100/2200 series, among many others, used ones'-complement arithmetic.

A remark on terminology: The system is referred to as "ones' complement" because the negation of a positive value x (represented as the bitwise NOT of x) can also be formed by subtracting x 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 x by subtracting x from a single large power of two that is congruent to +0.[1] 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 by bitwise complementing the magnitude.

Two's complement

8 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

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 (00000000). Negating a number (whether negative or positive) is done by inverting all the bits and then adding 1 to that result. Addition of a pair of two's-complement integers is the same as addition of a pair of unsigned numbers (except for detection of overflow, if that is done). 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' 0101001 0101100
2. Invert all of the bits to the left of that one 1010111 1010100

Excess-K

8 bit excess-127
Binary value Excess-127 interpretation Unsigned interpretation
00000000 −127 0
00000001 −126 1
... ... ...
01111111 0 127
10000000 1 128
... ... ...
11111111 +128 255

Excess-K, also called biased representation, uses a pre-specified number K as a biasing value. A value is represented by the unsigned number which is K greater than the intended value. Thus 0 is represented by K, and −K is represented by the all-zeros bit pattern. This is a generalization of the aforementioned two's-complement, which is virtually the excess-2N−1 representation.

This is a representation that is 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 also


Base −2

In conventional binary number systems, the base, or radix, is 2; thus the rightmost bit represents 20, the next bit represents 21, the next bit 22, and so on. However, a binary number system with base −2 is also possible. The rightmost bit represents (−2)0=+1, the next bit represents (−2)1=−2, the next bit (−2)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 4 bits.

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

See also

References

  1. ^ Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapter 4.1
  • Ivan Flores, The Logic of Computer Arithmetic, Prentice-Hall (1963)
  • Israel Koren, Computer Arithmetic Algorithms, A.K. Peters (2002), ISBN 1-56881-160-8

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Signed zero — is zero with an associated sign. In ordinary arithmetic, −0 = +0 = 0. However, in computing, some number representations allow for the existence of two zeros, often denoted by −0 (negative zero) and +0 (positive zero). This… …   Wikipedia

  • Signed-digit representation — of numbers indicates that digits can be prefixed with a − (minus) sign to indicate that they are negative. Signed digit representation can be used in low level software and hardware to accomplish fast high speed addition of integers because it… …   Wikipedia

  • 0 (number) — Zero redirects here. For other uses, see Zero (disambiguation). 0 −1 0 1 2 3 4 5 6 7 8 …   Wikipedia

  • Negative number — This thermometer is indicating a slightly negative …   Wikipedia

  • Serial Number Arithmetic — Many protocols and algorithms require the serialization or enumeration of related entities. For example, a communication protocol must know whether some packet comes before or after some other packet. The IETF (Internet Engineering Task Force)… …   Wikipedia

  • −0 (number) — −0 is the representation of negative zero or minus zero, a number that, in computing, exists in some signed number representations for integers, and in most floating point number representations. In mathematical terms there is no concept of a… …   Wikipedia

  • Integer (computer science) — In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values …   Wikipedia

  • Method of complements — Complement numbers on an adding machine c. 1910 In mathematics and computing, the method of complements is a technique used to subtract one number from another using only addition of positive numbers. This method was commonly used in mechanical… …   Wikipedia

  • Two's complement — The two s complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2 N for an N bit two s complement).A two s complement system or two s complement arithmetic is a… …   Wikipedia

  • Sign (mathematics) — The plus and minus symbols are used to show the sign of a number. Not to be confused with the sine function in trigonometry. In mathematics, the word sign refers to the property of being positive or negative. Every nonzero real number is either… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.