32 Chapter 2 Number Systems and Codes Table 2-4 Examples of 10's and 10's 9s' Number complement complement 9s'complements 1849 8151 8150 2067 7933 7932 100 9900 9899 9993 9992 8151 1849 1848 0 10000(=0) 9999 another number between 1 and rm-1.If D is 0,the result of the subtraction is" which has the form 100.-00,where there are a total ofn+I digits.We throw away the extra high-order digit and get there is only one rep resentation of zero in a radix-complement system. It seems from the definition that a subtraction operation is needed to com- pute the radix complement of D.However,this subtraction can be avoided by rewriting"as(1)+I and -D as (1)-D)+1.The number has the form mm···mm,where m=r-1 and there are n m's.For example, 10.000 equals 9,999+1.If we define the complement ofa digit d to ber-1-d then (r"1)-D is obtained by complementing the digits of D.Therefore,the radix complement of a number D is obtained by complementing the individual Table 2-5 Complement Digit complements Digit Binary Octal Decimal Hexadecimal 0 7 9 F 2 D 3 4 6 3 5 2 A 6 3 1 0 2 8 8 1 7 0 6 5 C D 0 Copyright1999 by John F.Wakerly Copying Prohibited
32 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited another number between 1 and r n − 1. If D is 0, the result of the subtraction is rn, which has the form 100 ⋅ ⋅ ⋅ 00, where there are a total of n + 1 digits. We throw away the extra high-order digit and get the result 0. Thus, there is only one representation of zero in a radix-complement system. It seems from the definition that a subtraction operation is needed to compute the radix complement of D. However, this subtraction can be avoided by rewriting rn as (r n − 1) + 1 and r n − D as ((r n − 1) − D) + 1. The number rn − 1 has the form mm ⋅ ⋅ ⋅ mm, where m = r − 1 and there are n m’s. For example, 10,000 equals 9,999 + 1. If we define the complement of a digit d to be r − 1 − d, then (rn − 1) − D is obtained by complementing the digits of D. Therefore, the radix complement of a number D is obtained by complementing the individual Table 2-4 Examples of 10’s and 9s’ complements. Number 10’s complement 9s’ complement 1849 8151 8150 2067 7933 7932 100 9900 9899 7 9993 9992 8151 1849 1848 0 10000 (= 0) 9999 Table 2-5 Digit complements. Complement Digit Binary Octal Decimal Hexadecimal 017 9 F 106 8 E 2–5 7 D 3–4 6 C 4–3 5 B 5–2 4 A 6–1 3 9 7–0 2 8 8–– 1 7 9–– 0 6 A– – – 5 B– – – 4 C– – – 3 D– – – 2 E– – – 1 F– – – 0 computing the radix complement
Section 2.5 Representation of Negative Numbers digits of D and adding 1.For example,the 10's complement of 1849 is 8150+1, or 8151.You should confirm that this trick also works for the other 10's-comple- ment examples above.Table 2-5 lists the digit complements for binary,octal decimal,and hexadecimal numbers. 2.5.4 Two's-Complement Representation For binary numbers,the radix complement is called the o's complement.The two's complemen MSB of a number in this system serves as the sign bit;a number is negative if and only if its MSB is 1.The decimal equivalent for a two's-complement binary er is computed the same way as for an unsigned number,except that the nstead of +2-1.The range of represent able num- weight of MSB bers is-(2")through +2-1 -1).Some 8-bit examples are shown below: 1710=000100012 -9910=100111012 complement bits complement bits 11101110 01100010 1 +1 111011112 =-1710 011000112=9910 1191o=01110111 -12710=10000001 complement bits complement bits 10001000 01111110 +1 +1 100010012=-11910 011111112=12710 010= 000000002 -12810=100000002 complement bits complement bits 11111111 01111111 +1 +1 1000000002=010 100000002=-12810 A carry out of the MSB position occurs in one case,as shown in color above.As in all two's-complement operations,this bit is ignored and only the low-order n bits of the result are used. In the two's-complement number system,zero is considered positive because its sign bit is 0.Since two's complement has only one representation of zero,we end up with one extra negative number,-(2),that doesn't have a pos- extra negative number itive counterpart. We can convert an n-bit two's-complement number X into an m-bit one,but some care is needed.If m >n,we must append m-n copies of X's sign bit to the left of (see Exercise 2.23).That is,we pad a positive number with 0s and a negative one with Is.this is called sign extension.If m<n,we discard X'sn-m sign extension Copyright 1999 by John F.Wakerly Copying Prohibited
Section 2.5 Representation of Negative Numbers 33 DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited digits of D and adding 1. For example, the 10’s complement of 1849 is 8150 + 1, or 8151. You should confirm that this trick also works for the other 10’s-complement examples above. Table 2-5 lists the digit complements for binary, octal, decimal, and hexadecimal numbers. 2.5.4 Two’s-Complement Representation For binary numbers, the radix complement is called the two’s complement. The MSB of a number in this system serves as the sign bit; a number is negative if and only if its MSB is 1. The decimal equivalent for a two’s-complement binary number is computed the same way as for an unsigned number, except that the weight of the MSB is −2n−1 instead of +2 n−1 . The range of representable numbers is −(2 n−1) through +(2 n−1 −1). Some 8-bit examples are shown below: A carry out of the MSB position occurs in one case, as shown in color above. As in all two’s-complement operations, this bit is ignored and only the low-order n bits of the result are used. In the two’s-complement number system, zero is considered positive because its sign bit is 0. Since two’s complement has only one representation of zero, we end up with one extra negative number, −(2n−1), that doesn’t have a positive counterpart. We can convert an n-bit two’s-complement number X into an m-bit one, but some care is needed. If m > n, we must append m − n copies of X’s sign bit to the left of X (see Exercise 2.23). That is, we pad a positive number with 0s and a negative one with 1s; this is called sign extension. If m < n, we discard X’s n − m 1710 = 00010001 ⇓ . 11101110 +1 2 complement bits −9910 = 10011101 ⇓ . 01100010 +1 2 complement bits 111011112 = −1710 011000112 = 9910 11910 = 01110111 ⇓ . 10001000 +1 complement bits −12710 = 10000001 ⇓ . 01111110 +1 complement bits 100010012 = −11910 011111112 = 12710 010 = 00000000 ⇓ . 11111111 +1 2 complement bits −12810 = 10000000 ⇓ . 01111111 +1 2 complement bits 1 000000002 = 010 100000002 = −12810 two’s complement weight of MSB extra negative number sign extension
34 Chapter 2 Number Systems and Codes leftmost bits:however,the result is valid only if all of the discarded bits are the same as the sign bit of the result(see Exercise 2.24). Most computers and other digital systems use the two's-complement sys- tem to represent negative numbers.However,for completeness,we'll also describe the diminished radix-complement and ones'-complement systems. *2.5.5 Diminished Radix-Complement Representation diminished radix In a diminished radix-complement system,the complement of an n-digit number complement system D is obtained by subtracting it from1.This can be accomplished by comple menting the individual digits of D,without adding 1 as in the radix-complement 9s'complement system.In decimal,this is called the 9s'complement,some examples are given in the last coumn of Table 2-on page 32. *2.5.6 Ones'-Complement Representation ones'complemen The diminished radix-complement system for binary numbers is called the ones' complement.As in two's complement,the most significant bit is the sign,0 if positive and I if negative.Thus there are two representations of zero,positive zero (00.00)and negative zero(11.11).Positive number representations are the same for both ones'and two's compler nega tive number representations differ by 1.A weight of-(2 is given to the most significant bit when computing the decimal equivalent of a ones'- 1710=000100012 -9910=100111002 111011102=-1710 011000112=9910 11910=011101112 -12710=100000002 100010002=-11910 011111112=12710 010=00000000(positive zero) 111111112=010(negative zero) The main advantages of the ones'-complement system are its symmetry and the ease of complementation.However,the adder design for ones'- complement numbers is somewhat trickier than a two's-compemadder (se Exercise 7.67).Also,zero-detecting circuits in a ones'-complement system *Throughout this book,optional sections are marked with an asterisk. Copyright 1999 by John F.Wakerly Copying Prohibited
34 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited leftmost bits; however, the result is valid only if all of the discarded bits are the same as the sign bit of the result (see Exercise 2.24). Most computers and other digital systems use the two’s-complement system to represent negative numbers. However, for completeness, we’ll also describe the diminished radix-complement and ones’-complement systems. *2.5.5 Diminished Radix-Complement Representation In a diminished radix-complement system, the complement of an n-digit number D is obtained by subtracting it from r n−1. This can be accomplished by complementing the individual digits of D, without adding 1 as in the radix-complement system. In decimal, this is called the 9s’ complement; some examples are given in the last column of Table 2-4 on page 32. *2.5.6 Ones’-Complement Representation The diminished radix-complement system for binary numbers is called the ones’ complement. As in two’s complement, the most significant bit is the sign, 0 if positive and 1 if negative. Thus there are two representations of zero, positive zero (00 ⋅⋅⋅ 00) and negative zero (11 ⋅⋅⋅ 11). Positive number representations are the same for both ones’ and two’s complements. However, negative number representations differ by 1. A weight of −(2n−1 − 1), rather than −2n−1, is given to the most significant bit when computing the decimal equivalent of a ones’- complement number. The range of representable numbers is −(2n−1 − 1) through +(2n−1 − 1). Some 8-bit numbers and their ones’ complements are shown below: The main advantages of the ones’-complement system are its symmetry and the ease of complementation. However, the adder design for ones’- complement numbers is somewhat trickier than a two’s-complement adder (see Exercise 7.67). Also, zero-detecting circuits in a ones’-complement system * Throughout this book, optional sections are marked with an asterisk. 1710 = 000100012 ⇓ . 111011102 = −1710 −9910 = 100111002 ⇓ . 011000112 = 9910 11910 = 011101112 ⇓ . 100010002 = −11910 −12710 = 100000002 ⇓ . 011111112 = 12710 010 = 000000002 (positive zero)0000000 ⇓ . 000 0111111112 = 010 (negative zero) diminished radixcomplement system 9s’ complement ones’ complement
Section 2.6 Two's-Complement Addition and Subtraction 35 either must check for both representations of zero,or must always convert 11.11to00.00. *2.5.7 Excess Representations Yes,the number of different systems for representing negative numbers is exces sive,but there's just one more for us to cover.In excess-B representation,an excess-B representation m-bit string whose unsigned integer value is M(0s M<2)represents the signed integer M-B,where B is called the bias of the number system. bias For examplean excessystem represents any numberin the range excess-2m-1 system -2m-through +2m-1-1 by the m-bit binary representation of +2m(which is always nonnegative and less than 2).The range of this representation is exactly the same as that of m-bit two'scompmentnumbers.In fact,the repre sentations of any number in the two systems are identical except for the sign bits, which are always opposite.(Note that this is true only when the bias is 2) The most cor mon use of excess representations is in floating-point num- ber systems(see References). 2.6 Two's-Complement Addition and Subtraction 2.6.1 Addition Rules A table of decimal numbers and their equivalents in different number systems Table 2-6,reveals why the two's complement is preferred for arithmetic opera- tions.If we start with 10002(-8o)and count up,we see that each successive two's-complement number all the way to 01112(+710)can be obtained by add- ingto the previousone ignoring any caries beyond the fourth bit position. The same cannot be said of signed-magnitude and ones'-complement numbers. Because ordinary addition is just an extension of counting,two's-complement to's-complement numbers can thus be added by ordinary binary addition,ignoring any carries addition beyond the MSB.The result will always be the correct sum as long as the range of the number system is not exceeded.Some examples of decimal addition and the corresponding 4-bit two's-complement additions confirm this: 43 0011 _2 1110 ++4 +0100 +-6+1010 0111 -8 11000 +6 0110 +4 0100 +-3+1101 +-7 +1001 +3 10011 3 1101 Copyright 1999 by John F.Wakerly Copying Prohibited
Section 2.6 Two’s-Complement Addition and Subtraction 35 DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited either must check for both representations of zero, or must always convert 11 ⋅⋅⋅ 11 to 00 ⋅⋅⋅ 00. *2.5.7 Excess Representations Yes, the number of different systems for representing negative numbers is excessive, but there’s just one more for us to cover. In excess-B representation, an m-bit string whose unsigned integer value is M (0 ≤ M < 2m) represents the signed integer M − B, where B is called the bias of the number system. For example, an excess−2m−1 system represents any number X in the range −2m−1 through +2m−1 − 1 by the m-bit binary representation of X + 2m−1 (which is always nonnegative and less than 2m). The range of this representation is exactly the same as that of m-bit two’s-complement numbers. In fact, the representations of any number in the two systems are identical except for the sign bits, which are always opposite. (Note that this is true only when the bias is 2m−1.) The most common use of excess representations is in floating-point number systems (see References). 2.6 Two’s-Complement Addition and Subtraction 2.6.1 Addition Rules A table of decimal numbers and their equivalents in different number systems, Table 2-6, reveals why the two’s complement is preferred for arithmetic operations. If we start with 10002 (−810) and count up, we see that each successive two’s-complement number all the way to 01112 (+710) can be obtained by adding 1 to the previous one, ignoring any carries beyond the fourth bit position. The same cannot be said of signed-magnitude and ones’-complement numbers. Because ordinary addition is just an extension of counting, two’s-complement numbers can thus be added by ordinary binary addition, ignoring any carries beyond the MSB. The result will always be the correct sum as long as the range of the number system is not exceeded. Some examples of decimal addition and the corresponding 4-bit two’s-complement additions confirm this: +3 + +4 0011 + 0100 −2 + −6 1110 + 1010 +7 0111 −8 11000 +6 + −3 0110 + 1101 +4 + −7 0100 + 1001 +3 10011 −3 1101 excess-B representation bias excess-2m−1 system two’s-complement addition
36 Chapter 2 Number Systems and Codes Table 2-Decimal and 4-bit numbers. Two's Ones' Signed Decimal Complement Complement Magnitude Excogs R 1000 0000 -7 1001 1000 1111 0001 -6 1010 1001 1110 0010 -5 1011 1010 1101 0011 -4 1100 1011 1100 0100 -3 1101 1100 1011 0101 1110 1101 1010 0110 -1 1111 1110 1001 0111 0 0000 1111or0000 1000or0000 1000 0001 0001 0001 1001 2 0010 0010 0010 1010 3 0011 0011 0011 1011 0100 0100 0100 1100 0101 0101 0101 1101 0110 0110 0110 1110 0111 0111 0111 1111 2.6.2 A Graphical View Another way to view the two's-complement system uses the 4-bit"counter" shown in Figure 2-3.Here we have shown the numbers in a circular or "modular"representation.The operation of this counter very closely mimics that of a real up/down counter circuit,which we'll study in Section 8.4.Starting 0000 Figure 2-3 1111 0001 A modular counting 1110.、 representation of 4-bit -1+0 、0010 2 two's-complement 1101、 +2 0011 numbers. -3 +3 Subtraction of oositive numbers 1100 4 +4十0100 Addition of positive number +5/ 1011 6 0101 6 7 1010 -8+7 0110 1001 1000 011 Copyright 1999 by John F.Wakerly Copying Prohibited
36 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited 2.6.2 A Graphical View Another way to view the two’s-complement system uses the 4-bit “counter” shown in Figure 2-3. Here we have shown the numbers in a circular or “modular” representation. The operation of this counter very closely mimics that of a real up/down counter circuit, which we’ll study in Section 8.4. Starting Table 2-6 Decimal and 4-bit numbers. Decimal Two’s Complement Ones’ Complement Signed Magnitude Excess 2m−1 −8 1000 — — 0000 −7 1001 1000 1111 0001 −6 1010 1001 1110 0010 −5 1011 1010 1101 0011 −4 1100 1011 1100 0100 −3 1101 1100 1011 0101 −2 1110 1101 1010 0110 −1 1111 1110 1001 0111 0 0000 1111 or 0000 1000 or 0000 1000 1 0001 0001 0001 1001 2 0010 0010 0010 1010 3 0011 0011 0011 1011 4 0100 0100 0100 1100 5 0101 0101 0101 1101 6 0110 0110 0110 1110 7 0111 0111 0111 1111 0000 1000 0001 0010 0011 1011 0101 1100 1101 1110 1111 1010 0110 1001 0111 0100 +0 –8 –1 +1 –7 +7 –2 +2 –3 +3 –4 +4 –5 +5 –6 +6 Subtraction of positive numbers Addition of positive numbers Figure 2-3 A modular counting representation of 4-bit two’s-complement numbers