Signed number representations
Encyclopedia
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.
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.
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).
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. 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.
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:
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.
, 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.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, signed number representations are required to encode negative numbers in binary number systems.
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, negative numbers in any base are represented by prefixing them with a − sign. However, in computer hardware
Hardware
Hardware is a general term for equipment such as keys, locks, hinges, latches, handles, wire, chains, plumbing supplies, tools, utensils, cutlery and machine parts. Household hardware is typically sold in hardware stores....
, numbers are represented in binary only without extra symbols, requiring a method of encoding
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
the minus sign. The four best-known methods of extending the binary numeral system
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
to represent signed numbers are: sign-and-magnitude, ones' complement, two's complement
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...
, 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.
Sign-and-magnitude method
You may first approach the problem of representing a number's sign by allocating one sign bitSign bit
In computer science, the sign bit is a bit in a computer numbering format that indicates the sign of a number. In IEEE format, the sign bit is the leftmost bit...
to represent the sign: set that bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
(often the most significant bit
Most significant bit
In computing, the most significant bit is the bit position in a binary number having the greatest value...
) 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
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
). Hence in a byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
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
IBM 7090
The IBM 7090 was a second-generation transistorized version of the earlier IBM 709 vacuum tube mainframe computers and was designed for "large-scale scientific and technological applications". The 7090 was the third member of the IBM 700/7000 series scientific computers. The first 7090 installation...
) used this representation, perhaps because of its natural relation to common usage. Sign-and-magnitude is the most common way of representing the significand
Significand
The significand is part of a floating-point number, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent an integer or a fraction.-Examples:...
in floating point
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
values.
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
Carry flag
In computer processors the carry flag is a single bit in a system status register used to indicate when an arithmetic carry or borrow has been generated out of the most significant ALU bit position...
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
PDP-1
The PDP-1 was the first computer in Digital Equipment Corporation's PDP series and was first produced in 1960. It is famous for being the computer most important in the creation of hacker culture at MIT, BBN and elsewhere...
, CDC 160A
CDC 160A
The CDC 160 and CDC 160-A were 12-bit minicomputers built by Control Data Corporation from 1960 to 1965. The 160 was designed by Seymour Cray - reportedly over a long three-day weekend...
and UNIVAC 1100/2200 series
UNIVAC 1100/2200 series
The UNIVAC 1100/2200 series is a series of compatible 36-bit computer systems, beginning with the UNIVAC 1107 in 1962, initially made by Sperry Rand...
, 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
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
to +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 by bitwise complementing the magnitude.
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
| 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
IEEE floating-point standard
IEEE 754–1985 was an industry standard for representingfloating-pointnumbers in computers, officially adopted in 1985 and superseded in 2008 byIEEE 754-2008. During its 23 years, it was the most widely used format for...
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.
Base −2
In conventional binary number systems, the base, or radixRadix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
, 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.| Decimal | Unsigned | Sign and magnitude | Ones' complement | Two's complement | Excess-7 (biased) | Base −2 |
|---|---|---|---|---|---|---|
| +16 | ||||||
| +15 | 1111 | |||||
| +14 | 1110 | |||||
| +13 | 1101 | |||||
| +12 | 1100 | |||||
| +11 | 1011 | |||||
| +10 | 1010 | |||||
| +9 | 1001 | |||||
| +8 | 1000 | 1111 | ||||
| +7 | 0111 | 0111 | 0111 | 0111 | 1110 | |
| +6 | 0110 | 0110 | 0110 | 0110 | 1101 | |
| +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 | 0000 | 0000 | ||||
| 0 | 0000 | 0000 | 0111 | 0000 | ||
| −0 | 1000 | 1111 | ||||
| −1 | 1001 | 1110 | 1111 | 0110 | 0011 | |
| −2 | 1010 | 1101 | 1110 | 0101 | 0010 | |
| −3 | 1011 | 1100 | 1101 | 0100 | 1101 | |
| −4 | 1100 | 1011 | 1100 | 0011 | 1100 | |
| −5 | 1101 | 1010 | 1011 | 0010 | 1111 | |
| −6 | 1110 | 1001 | 1010 | 0001 | 1110 | |
| −7 | 1111 | 1000 | 1001 | 0000 | 1001 | |
| −8 | 1000 | 1000 | ||||
| −9 | 1011 | |||||
| −10 | 1010 | |||||
| −11 |
See also
- Binary-coded decimalBinary-coded decimalIn computing and electronic systems, binary-coded decimal is a digital encoding method for numbers using decimal notation, with each decimal digit represented by its own binary sequence. In BCD, a numeral is usually represented by four bits which, in general, represent the decimal range 0 through 9...
- Computer numbering formatsComputer numbering formatsA computer number format is the internal representation of numeric values in digital computer and calculator hardware and software.-Bits:The concept of a bit can be understood as a value of either 1 or 0, on or off, yes or no, true or false, or encoded by a switch or toggle of some kind...
- Method of complementsMethod of complementsIn 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 calculators and is still used in modern computers...
- Balanced ternaryBalanced ternaryBalanced ternary is a non-standard positional numeral system , useful for comparison logic. It is a ternary system, but unlike the standard ternary system, the digits have the values −1, 0, and 1...