algorithm binary bitmanipulation c++ code coding cs cs101 cs333 development discretemath javacert javanjatkokurssi math programming school science signed theory

My tags:

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Computer numbering formats. (Discuss)

In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a "−" sign. However, in computer hardware, 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. Modern computers typically use the two's-complement representation, but other representations are used in some circumstances.

Contents 1 Sign-and-magnitude 2 Ones' complement 3 Two's complement 4 Excess-N 4.1 See also 5 Base −2 5.1 See also 6 Comparison table 7 See also 8 References 9 Notes

[edit] Sign-and-magnitude

8 bit signed magnitude

Binary	Signed	Unsigned
00000000	0	0
00000001	1	1
...	...	...
01111111	127	127
10000000	−0	128
...	...	...
11111111	−127	255

One 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 −127₁₀ to +127₁₀ 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. (Many decimal computers also used sign-and-magnitude.)

[edit] 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
...	...	...
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 in a conventional eight-bit byte is −127₁₀ to +127₁₀.

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 orthography: 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.

The Internet protocols IPv4, ICMP, UDP and TCP all use the same 16-bit 1's complement checksum algorithm. Although most computers lack "end-around carry" hardware, the extra complexity is accepted because "it is equally sensitive to errors in all bit positions".^[2] In UDP, the all 0s representation of zero indicates that the optional checksum feature has been omitted. The other representation, FFFF, indicates a checksum value of 0.^[3] (Checksums are mandatory in IPv4, TCP and ICMP; they were omitted from IPv6).

Note that the ones' complement representation of a negative number can be obtained from the sign-magnitude representation merely by bitwise complementing the magnitude.

[edit] 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 above table.

An easier method to get the two's complement of a number 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

[edit] Excess-N

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-N, also called biased representation, uses a pre-specified number N as a biasing value. A value is represented by the unsigned number which is N greater than the intended value. Thus 0 is represented by N, and −N is represented by the all-zeros bit pattern.

This 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.

[edit] See also

• Excess-3
• two's complement

[edit] Base −2

In conventional binary number systems, the base, or radix, 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)²=+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.

[edit] See also

• Negative base
• Balanced ternary

[edit] 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
+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	0000	0000	0000	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

[edit] See also

• Computer numbering formats
• Excess-3
• Method of complements
• Two's complement

[edit] 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

[edit] Notes

1. ^ Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapter 4.1
2. ^ R Braden et al., Computing the Internet Checksum, RFC 1071, [1]
3. ^ RFC 768