Signed number representations
Encyclopedia : S : SI : SIG : Signed number representations
In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a "−" sign. However, on a computer, there are various ways of representing a number's sign. This article deals with four methods of extending the binary numeral system to represent signed numbers: sign-and-magnitude, ones' complement, two's complement, and excess N.
For most purposes, modern computers typically use the two's complement representation, but other representations are used in some circumstances.
Sign-and-magnitude
One may first approach this 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. A consequence of this representation is that there are two ways to represent 0, 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. (Many decimal computers also used sign-and-magnitude.)
One's complement
Alternatively, a system known as one's-complement could be used to represent negative numbers. The one's complement form of a binary number is the bitwise NOT applied to it—the complement of its positive counterpart. Like sign-and-magnitude representation, one's complement will have two representations of 0: 00000000 (+0) and 11111111 (−0).
As an example, the one's complement form of 00101011 (43) becomes 11010100 (−43). The range of signed numbers using one's complement in a conventional eight-bit byte is −12710 to +12710.
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 case of the addition of −1 (11111110) to +2 (00000010). The binary addition alone gives 00000000—not the correct answer! 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 and UNIVAC 1100/2200 series, among many others, used one's-complement arithmetic.
(A remark on terminology: a more precise naming would be "ones' complement", as this method uses a complement to a long string of ones, while the two's complement uses a single power of two.Donald Knuth: ''The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapter 4.1)
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.
For example, if an integer is expressed by 8 bits, the values are:
two's complement unsigned binary value value 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 255In 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 above table.
Excess-N
- Main article (for N = 3): Excess-3
For example, the Excess-5 representation in 4 bits is as follows:
decimal binary excess-5 value 0 0000 -5 1 0001 -4 2 0010 -3 3 0011 -2 4 0100 -1 5 0101 0 6 0110 1 ... ... ... 15 1111 10This is a representation that is now primarily used within 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.
Comparison table
The following table compares the representation of the integers between positive and negative eight (inclusive) using 4 bits.
| Decimal | Unsigned | Sign and Magnitude | One's Complement | Two's Complement | Excess-7 (Biased) |
|---|---|---|---|---|---|
| +8 | 1000 | style="background: #ececec" | N/A | style="background: #ececec" | N/A | style="background: #ececec" | N/A | 1111 |
| +7 | 0111 | 0111 | 0111 | 0111 | 1110 |
| +6 | 0110 | 0110 | 0110 | 0110 | 1101 |
| +5 | 0101 | 0101 | 0101 | 0101 | 1100 |
| +4 | 0100 | 0100 | 0100 | 0100 | 1011 |
| +3 | 0011 | 0011 | 0011 | 0011 | 1010 |
| +2 | 0010 | 0010 | 0010 | 0010 | 1001 |
| +1 | 0001 | 0001 | 0001 | 0001 | 1000 |
| (+)0 | 0000 | 0000 | 0000 | 0000 | 0111 |
| (−)0 | style="background: #ececec" | N/A | 1000 | 1111 | style="background: #ececec" | N/A | style="background: #ececec" | N/A |
| −1 | style="background: #ececec" | N/A | 1001 | 1110 | 1111 | 0110 |
| −2 | style="background: #ececec" | N/A | 1010 | 1101 | 1110 | 0101 |
| −3 | style="background: #ececec" | N/A | 1011 | 1100 | 1101 | 0100 |
| −4 | style="background: #ececec" | N/A | 1100 | 1011 | 1100 | 0011 |
| −5 | style="background: #ececec" | N/A | 1101 | 1010 | 1011 | 0010 |
| −6 | style="background: #ececec" | N/A | 1110 | 1001 | 1010 | 0001 |
| −7 | style="background: #ececec" | N/A | 1111 | 1000 | 1001 | 0000 |
| −8 | style="background: #ececec" | N/A | style="background: #ececec" | N/A | style="background: #ececec" | N/A | 1000 | style="background: #ececec" | N/A |
See also
References
- Ivan Flores, The Logic of Computer Arithmetic, Prentice-Hall (1963)
- Israel Koren, Computer Arithmetic Algorithms, A.K. Peters (2002), ISBN 1-56881-160-8
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.