Section 2.3 General Positional Number System Conversions 27 Tabl 2-2 Conversion methods for common radices. Conversion Method Example Binary to Octal Substitution 101110110012=101110110012=2731g Hexadecimal Substitution 101110110012=101110110012=5D916 Decimal Summation 101110110012=1.1024+0.512+1.256+1.128+1.64 +0.32+1.16+1.8+0.4+0.2+1.1=149710 Octal to Binary Substitution 1234s =001 010 011 1002 Hexadecimal Substitution 1234s =001 010 011 1002=0010 1001 11002 =29C16 Decimal Summation 1234g=1.512+264+3.8+4.1=66810 Hexadecimal to Binary Substitution CODE16=1100 0000 1101 11102 Octal Substitution C0DE16=11000000110111102=11000000110111102=140336g Decimal Summation C0DE16=12.4096+0.256+13.16+14.1=4937410 Decimal to Binary Division 1082-54 remainder (LSB) +2-27 remainder( +2=13 remainder 1 +2=6 remainder 1 +2=3 remainder 0 +2=1 remainder 1 +2=0 remainder 1 (MSB) 10810=1101100: Octal Division 13 remainder 4 (least significant digit) +8=0 remainder I (most significant digit) 10810=154g Hexadecimal Division 1080+16=6 remainder 12 (least significant digit) +16=0 remainder 6 (most significant digit) 10810=6C16 Copyright1999 by John F.Wakerly Copying Prohibited
Section 2.3 General Positional Number System Conversions 27 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 Table 2-2 Conversion methods for common radices. Conversion Method Example Binary to Octal Substitution 101110110012 = 10 111 011 0012 = 27318 Hexadecimal Substitution 101110110012 = 101 1101 10012 = 5D916 Decimal Summation 101110110012 = 1 ⋅ 1024 + 0 ⋅ 512 + 1 ⋅ 256 + 1 ⋅ 128 + 1 ⋅ 64 + 0 ⋅ 32 + 1 ⋅ 16 + 1 ⋅ 8 + 0 ⋅ 4 + 0 ⋅ 2 + 1 ⋅ 1 = 149710 Octal to Binary Substitution 12348 = 001 010 011 1002 Hexadecimal Substitution 12348 = 001 010 011 1002 = 0010 1001 11002 = 29C16 Decimal Summation 12348 = 1 ⋅ 512 + 2 ⋅ 64 + 3 ⋅ 8 + 4 ⋅ 1 = 66810 Hexadecimal to Binary Substitution C0DE16 = 1100 0000 1101 11102 Octal Substitution C0DE16 = 1100 0000 1101 11102 = 1 100 000 011 011 1102 = 1403368 Decimal Summation C0DE16 = 12 ⋅ 4096 + 0 ⋅ 256 + 13 ⋅ 16 + 14 ⋅ 1 = 4937410 Decimal to Binary Division 10810 ÷ 2 = 54 remainder 0 (LSB) ÷2 = 27 remainder 0 ÷2 = 13 remainder 1 ÷2 = 6 remainder 1 ÷2 = 3 remainder 0 ÷2 = 1 remainder 1 ÷2 = 0 remainder 1 (MSB) 10810 = 11011002 Octal Division 10810 ÷ 8 = 13 remainder 4 (least significant digit) ÷8 = 1 remainder 5 ÷8 = 0 remainder 1 (most significant digit) 10810 = 1548 Hexadecimal Division 10810 ÷ 16 = 6 remainder 12 (least significant digit) ÷16 = 0 remainder 6 (most significant digit) 10810 = 6C16
28 Chapter 2 Number Systems and Codes Table 2-3 Binary addition and Cin or bin x V Cout bout subtraction table 0 0 0 0 0 0 0 1 0 0 0 0 1 1 00 0 0 1 0 0 1 1 1 1 1 1 2.4 Addition and Subtraction of Nondecimal Numbers Addition and subtraction of nondecimal numbers by hand uses the same tech- nique that we learned in grammar school for decimal numbers;the only catch is binary addition Table 2-3 is the addition and subtraction table for binary digits.To add two binary numbers Xand y,we add together the least significant bits with an initial carry (c producing carry (and sum (s)bits according to the table.We continue processing bits from right to left,adding the carry out of each column into the next column's sum. Two examples of decimal additions and the corresponding binary additions are shown in Figure,arrow to indicate acarry of The same examples are repeated below along with two more,with the carries shown as a bit string C: 101111000 001011000 190 10111110 173 10101101 Y+141 +10001101 +44 +00101100 X+Y331 101001011 X+Y217 11011001 011111110 c 000000000 X 127 01111111 X 170 10101010 +63 +00111111 +85 +01010101 X+Y190 10111110 X+y255 11111111 binary subtraction Binary subtraction is performed similarly,using borrows (bin and bout) instead of carries between steps,and producing a difference bit d.Two examples minuend of decim subtractions and the corresponding binary subtractions are shown in subtrahend Figure 2-2.As in decimal subtraction,the binary minuend values in the columns are modified when borrows occur,as shown by the colored arrows and bits.The Copyright 1999 by John F.Wakerly Copying Prohibited
28 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.4 Addition and Subtraction of Nondecimal Numbers Addition and subtraction of nondecimal numbers by hand uses the same technique that we learned in grammar school for decimal numbers; the only catch is that the addition and subtraction tables are different. Table 2-3 is the addition and subtraction table for binary digits. To add two binary numbers X and Y, we add together the least significant bits with an initial carry (cin) of 0, producing carry (cout) and sum (s) bits according to the table. We continue processing bits from right to left, adding the carry out of each column into the next column’s sum. Two examples of decimal additions and the corresponding binary additions are shown in Figure 2-1, using a colored arrow to indicate a carry of 1. The same examples are repeated below along with two more, with the carries shown as a bit string C: Binary subtraction is performed similarly, using borrows (bin and bout) instead of carries between steps, and producing a difference bit d. Two examples of decimal subtractions and the corresponding binary subtractions are shown in Figure 2-2. As in decimal subtraction, the binary minuend values in the columns are modified when borrows occur, as shown by the colored arrows and bits. The Table 2-3 Binary addition and subtraction table. cin or bin xy cout s bout d 0 00 0 0 0 0 0 01 0 1 1 1 0 10 0 1 0 1 0 11 1 0 0 0 1 00 0 1 1 1 1 01 1 0 1 0 1 10 1 0 0 0 1 11 1 1 1 1 C X Y 190 +141 101111000 10111110 + 10001101 C X Y 173 + 44 001011000 10101101 + 00101100 X + Y 331 101001011 X + Y 217 11011001 C X Y 127 + 63 011111110 01111111 + 00111111 C X Y 170 + 85 000000000 10101010 + 01010101 X + Y 190 10111110 X + Y 255 11111111 binary addition binary subtraction minuend subtrahend
Section2.4 Addition and Subtraction of Nondecimal Numbers 29 111 1 11 190 101110 173 10101101 y+141 +10001101 Y+44 +00101100 X+y331101001011 X+y217 11011001 Figure 2-1 Examples of decimal and corresponding binary additions examples from the figure are repeated below along with two more,this time showing the borrows as a bit string B: 001111100 011011010 229 11100101 210 11010010 -46 -00101110 Y -109 -01101101 X-Y 183 10110111 X-Y 101 01100101 B 010101010 B 000000000 X 170 10101010 X 221 11011101 -85 -01010101 -76 -01001100 X-Y 85 01010101 x-Y 145 10010001 A very common use of subtraction in computers is to compare two numbers.For omparing numbers example,if the e operation X -Y produces a borrow out of the most significant bit position.thenYis less than y:otherwise.is greater than or equal to y The rela- tionship between carries and borrow in adders and subtractors will be explored in Sec ion 5.10. Addition and subtraction tables can be developed for octal and hexadeci mal digits,or any other desired radix.However,few computer engineers bother to memorize these tables.Ifyou rarely need to manipulate nondecimal numbers Figure 2-2 Examples of decimal and corres binary subractions agtopelesteoUghhreecohum 1 (the 010111010 010100110010 minuend X229 X210 10/g0/0 subtrahend y=46 -001011 y-=109 -01101101 Y-) 183 101101 x-Y 101 01100101 Copyright 1999 by John F.Wakerly Copying Prohibited
Section 2.4 Addition and Subtraction of Nondecimal Numbers 29 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 examples from the figure are repeated below along with two more, this time showing the borrows as a bit string B: A very common use of subtraction in computers is to compare two numbers. For example, if the operation X − Y produces a borrow out of the most significant bit position, then X is less than Y; otherwise, X is greater than or equal to Y. The relationship between carries and borrow in adders and subtractors will be explored in Section 5.10. Addition and subtraction tables can be developed for octal and hexadecimal digits, or any other desired radix. However, few computer engineers bother to memorize these tables. If you rarely need to manipulate nondecimal numbers, B X Y 229 − 46 001111100 11100101 − 00101110 B X Y 210 −109 011011010 11010010 − 01101101 X − Y 183 10110111 X − Y 101 01100101 B X Y 170 − 85 010101010 10101010 − 01010101 B X Y 221 − 76 000000000 11011101 − 01001100 X − Y 85 01010101 X − Y 145 10010001 190 + 141 331 1 1 0 + 1 0 0 1 1111 1 11 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 X Y X + Y X Y X + Y 173 + 44 217 1 0 1 + 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 Figure 2-1 Examples of decimal and corresponding binary additions. 229 – 46 183 – 1 0 1 0 0 1 1 0 1 1 0 0 0 10 10 0 1 10 0 10 10 1 1 10 10 1 0 1 X Y X – Y X Y X – Y minuend subtrahend difference 210 – 109 101 – 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 The borrow ripples through three columns to reach a borrowable 1, i.e., 100 = 011 (the modified bits) + 1 (the borrow) After the first borrow, the new subtraction for this column is 0–1, so we must borrow again. Must borrow 1, yielding the new subtraction 10–1 = 1 1001 1 1 0 1 1 1 11 10 1 Figure 2-2 Examples of decimal and corresponding binary subtractions. comparing numbers
30 Chapter 2 Number Systems and Codes then it's easy enough on those occasions to convert them to decimal,calculate resuts,and conver back.On hand,if you must perform calculations in binary,octal,or hexadecimal frequently,then you should ask Santa for a pro- grammer's"hex calculator"from Texas Instruments or Casio. If the calculator's battery wears out,some mental shortcuts can be used to facilitate nondecimal arithmetic.In general,each column addition (or subtrac tion)can be done by converting the column digits to decimal,adding in decimal. and converting the result to corresponding sum and carry digits in the nondeci mal radix.(A carry is produced whenever the column sum equals or exceeds the radix.)Since the addition is done in decimal,we rely on our knowledge of the decimal addition table;the only new thing that we need to learn is the conversion from decimal to nondecimal digits and vice versa.The sequence of steps for hexadecimal addition 1100 0 19B916 1 11 9 Y +C7E616 +12 7 14 X+Y E19F16 14 17 25 15 1416+116+9 15 E 9 2.5 Representation of Negative Numbers So far,we have dealt only with positive numbers,but there are many ways to rep- resent negative numbers.In everyday business,we use the signed-magnitud system,discussed next.However,most computers use one of the complement number systems that we introduce later. 2.5.1 Signed-Magnitude Representation signed-magnitude In the signed-magnitude system,a number consists of a magnitude and a symbol system indicating whether the magnitude is positive or negative.Thus,we interpret dec- imal numbers+98,-57,+123.5,and-13 in the usual way,and we also assume that the sign is“+ if no sign symbol is written.There are two possible represen- tations of zero,“+O”and“-O”,but both have the same value. The signed-magnitude system is applied to binary numbers by using an sign bit extra bit po tion to represent the sign (the sign)Traditionally,the most sig- nificant bit(MSB)of a bit string is used as the sign bit(0=plus,1 =minus),and the lower-order bits contain the magnitude.Thus.we can write several 8-bit signed-magnitude integers and their decimal equivalents: 010101012=+8510 110101012=-8510 011111112=+12710 111111112=-12710 000000002=+010 100000002=-010 Copyright 1999 by John F.Wakerly Copying Prohibited
30 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 then it’s easy enough on those occasions to convert them to decimal, calculate results, and convert back. On the other hand, if you must perform calculations in binary, octal, or hexadecimal frequently, then you should ask Santa for a programmer’s “hex calculator” from Texas Instruments or Casio. If the calculator’s battery wears out, some mental shortcuts can be used to facilitate nondecimal arithmetic. In general, each column addition (or subtraction) can be done by converting the column digits to decimal, adding in decimal, and converting the result to corresponding sum and carry digits in the nondecimal radix. (A carry is produced whenever the column sum equals or exceeds the radix.) Since the addition is done in decimal, we rely on our knowledge of the decimal addition table; the only new thing that we need to learn is the conversion from decimal to nondecimal digits and vice versa. The sequence of steps for mentally adding two hexadecimal numbers is shown below: 2.5 Representation of Negative Numbers So far, we have dealt only with positive numbers, but there are many ways to represent negative numbers. In everyday business, we use the signed-magnitude system, discussed next. However, most computers use one of the complement number systems that we introduce later. 2.5.1 Signed-Magnitude Representation In the signed-magnitude system, a number consists of a magnitude and a symbol indicating whether the magnitude is positive or negative. Thus, we interpret decimal numbers +98, −57, +123.5, and −13 in the usual way, and we also assume that the sign is “+” if no sign symbol is written. There are two possible representations of zero, “+0” and “−0”, but both have the same value. The signed-magnitude system is applied to binary numbers by using an extra bit position to represent the sign (the sign bit). Traditionally, the most significant bit (MSB) of a bit string is used as the sign bit (0 = plus, 1 = minus), and the lower-order bits contain the magnitude. Thus, we can write several 8-bit signed-magnitude integers and their decimal equivalents: C X Y + 1 1 C 1 9 7 0 B E 0 9 6 16 16 + 1 1 12 1 9 7 0 11 14 0 9 6 X + Y E19F 16 14 14 E 17 16+1 1 25 16+9 9 15 15 F 010101012 = +8510 110101012 = –8510 011111112 = +12710 111111112 = –12710 000000002 = +010 100000002 = –010 hexadecimal addition signed-magnitude system sign bit
Section 2.5 Representation of Negative Numbers 31 The signed-magnitude system has an equal number of positive and nega- tive integers.An n-bit signed-magnitude integer lies within the range-(2-1) through+(2-1-1),and there are two possible representations ofze Now suppose that we wanted to build a digital logic circuit that adds signed-magnitude numbers.The circuit must examine the signs of the addends signed-magnitude to determine what to do with the magnitudes.If the signs are the same,it must adder add the magnitudes and give te same sign.Ifthe must compare the magnitudes,subtract the smaller from the larger,and give the result the sign of the larger.All of these“ifs,”“adds,"“subtracts,”and“com- pares"translate into a lot of logic-circuit complexity.Adders for complemen number systems are much simpler,as we'll show next.Perhaps the one redeem- ing feature of a signed-magnitude system is that,once we know how to build a ned-magnitude adder,a signed-magnitude subtractor is almost trivial to d.m build-it need only change the sign of the subtrahend and pass it along with the minuend to an adder 2.5.2 Complement Number Systems While the signed-magnitude system negates a number by changing its sign,a complement number system negates a number by taking its complement as complement number defined by the system.Taking the complement is more difficult than changing system the sign,but two numbers in a complement number system can be added or sub- tracted directly without the sign and magnitude checks required by the signed- magnitude system.We shall describe two complement number systems,called the"radix complement"and the"diminished radix-complement." In any complement number system,we normally deal with a fixed number of digits,say n.(However,we can increase the number of digits by "sign exten- sion"as shown in Exercise 2.23,and decrease the number by truncating high- order digits as shown in Exercise 2.24.)We further assume that the radix isr,and that numbers have the form D=drdr2·ddo The radix point is on the right and so the number is an integer.If an operation produces a result that requires more than n digits,we throw away the extra high order digit(s).If a number D is complemented twice,the result is D. 2.5.3 Radix-Complement Representation In a radix-complement system,the complement of an n-digit number is obtained radix-complement by subtracting it from r".In the decimal number system,the radix complement system is called the 10's complement.Some examples using 4-digit decimal numbers 10's complement (and subtraction from10.000)are shown in Table24. By definition,the radix complement of an n-digit number D is obtained by subtracting it from r".If D is between I and r"-1.this subtraction produces Copyright 1999 by John F.Wakerly Copying Prohibited
Section 2.5 Representation of Negative Numbers 31 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 The signed-magnitude system has an equal number of positive and negative integers. An n-bit signed-magnitude integer lies within the range −(2n−1−1) through +(2n−1−1), and there are two possible representations of zero. Now suppose that we wanted to build a digital logic circuit that adds signed-magnitude numbers. The circuit must examine the signs of the addends to determine what to do with the magnitudes. If the signs are the same, it must add the magnitudes and give the result the same sign. If the signs are different, it must compare the magnitudes, subtract the smaller from the larger, and give the result the sign of the larger. All of these “ifs,” “adds,” “subtracts,” and “compares” translate into a lot of logic-circuit complexity. Adders for complement number systems are much simpler, as we’ll show next. Perhaps the one redeeming feature of a signed-magnitude system is that, once we know how to build a signed-magnitude adder, a signed-magnitude subtractor is almost trivial to build—it need only change the sign of the subtrahend and pass it along with the minuend to an adder. 2.5.2 Complement Number Systems While the signed-magnitude system negates a number by changing its sign, a complement number system negates a number by taking its complement as defined by the system. Taking the complement is more difficult than changing the sign, but two numbers in a complement number system can be added or subtracted directly without the sign and magnitude checks required by the signedmagnitude system. We shall describe two complement number systems, called the “radix complement” and the “diminished radix-complement.” In any complement number system, we normally deal with a fixed number of digits, say n. (However, we can increase the number of digits by “sign extension” as shown in Exercise 2.23, and decrease the number by truncating highorder digits as shown in Exercise 2.24.) We further assume that the radix is r, and that numbers have the form D=dn–1dn–2···d1d0 . The radix point is on the right and so the number is an integer. If an operation produces a result that requires more than n digits, we throw away the extra highorder digit(s). If a number D is complemented twice, the result is D. 2.5.3 Radix-Complement Representation In a radix-complement system, the complement of an n-digit number is obtained by subtracting it from r n. In the decimal number system, the radix complement is called the 10’s complement. Some examples using 4-digit decimal numbers (and subtraction from 10,000) are shown in Table 2-4. By definition, the radix complement of an n-digit number D is obtained by subtracting it from r n. If D is between 1 and rn − 1, this subtraction produces signed-magnitude adder signed-magnitude subtractor complement number system radix-complement system 10’s complement