Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

 

Signed number representations

(Redirected from One's complement)

In mathematics, signed numbers in some arbitrary base is done in the usual way, by prefixing it with a "-" sign. However, on a computer, there is no single way 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.

Contents

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 (positive) magnitude. Hence in a byte with only seven 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.

Ones' complement

Alternatively, a system known as ones'-complement could be used to represent negative numbers. The ones' complement form of a binary number is the bitwise NOT applied to it - the complement of its positive counterpart. Like Sign-and-magnitude representation, ones' complement will have 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 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 ones'-complement arithmetic.

Two's complement

See Two's complement for the main article

In circumventing the problems of multiple representations of 0 and the need for the end-around carry, we introduce a system called "two's complement". In two's complement, negative numbers are represented by taking the ones' complement form of the absolute value of that number and then adding one to the value as if it were unsigned.

For example, if an integer is expressed by 8 bits,

digits  binary    actual value
0       00000000  0
1       00000001  1
....
126     01111110  126
127     01111111  127
128     10000000  -128
129     10000001  -127
130     10000010  -126
....
254     11111110  -2
255     11111111  -1

Usually, the computer's central processing unit (CPU) can use both signed and unsigned variables. In typical computer architectures there is no way to determine if a given digit is signed or unsigned at runtime because 255 and -1, for instance, appear the same in memory, and both addition, subtraction and multiplication are identical between signed and unsigned values, assuming overflow is ignored, by simply cutting off higher bits than can be stored. The datatype of the value dictates which operation should be applied.

In two's-complement, there is only one zero (00000000). Negating a negative number involves the same operation: complementing, then adding 1. To add two two's-complement integers, treat them as unsigned numbers, add them, and ignore any potential carry over (this is essentially the great advantage that two's-complement has over the other conventions).


Excess N

This is a representation that is primarily used in floating point numbers. It uses a specific number as a base. Under excess-N, a standard number representation is 'shifted' downwards such that the number 0 is represented as N as a binary number. For example the Excess 5 representation for 4 bits is as follows:

digits  binary  actual value
     0  0000    -5
     1  0001    -4
     2  0010    -3
     3  0011    -2
     4  0100    -1
     5  0101     0
....
    15  1111    10

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.

This representation scheme is also known as biasing, in which terminology the base number is called the bias.

Last updated: 05-07-2005 03:52:56
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy