Number systems - University of St Thomas数字系统-圣汤姆斯大学.doc

NumberSystemsPositional number systemsWhole numbersFractionsAccuracyCopyright 1993-95, Thomas P. SturmConcept of a Positional Number SystemWhat does 4,752 (base 10) represent (in base 10)?4 x 100040004 x 103+7 x 1007007 x 102+5 x 10505 x 101+2 x 122 x 100So what does 1011 (base 2) represent (in base 10)?1 x 881 x 230 x 400 x 221 x 221 x 211 x 111 x 20While this makes a nice definition, it is far too much work for practical use - binary numbers get to be long Counting RevisitedDecimalBinaryOctalHexadecimal000011112102231133410044510155611066711177810001089100111910101012A11101113B12110014C13110115D14111016E15111117F161000020101710001211118100102212191001123132010100241421101012515221011026162310111271724110003018251100131192611010321A2711011331B2811100341C2911101351D3011110361E3111111371F321000004020Faster Conversion of Binary to DecimalDibble-Dabble, Horners Method, Algorithm 1.11. Start at the left, start with 02. Add in leading digit3. If theres another digit, multiply total by 2, add in next digit, repeat this step until you reach the radix (binary) point.Ex:11010 (binary) converted to base 10 is:0+ 11x 22+ 13x 26+ 06x 212+ 113x 226+ 026Even Faster in Your HeadEx:11010010110 (binary) converted to base 10 is:(in your head 1,3,6,13,26,52,105,210,421,843,1686)Which has just got to be a lot quicker than1024+ 512+ 128+ 16+ 4+ 2(not even counting the time it takes to generate the powers of 2)Fast Decimal to Binary Conversion(Dibble-Dabble, Horners Method, Algorithm 1.2)Since all even numbers end in 0 (binary), and all odd numbers end in 1 (binary), and since division by 2 yields a 0 remainder for even numbers and a 1 remainder for odd numbers, the remainder after division by 2 gives you the LSB (least significant bit) of the corresponding binary number.Just repeat this process until you get a 0 quotientEx: Convert 75 (decimal) to binary2 | 752 | 37+12 | 18+12 | 9+02 | 4+12 | 2+02 | 1+0 0+1Now, the trick to remember, the LSB is ON TOP, so read the answer from the bottom up:75 (decimal) = 1001011 (binary)Converting Other BasesEx: Convert 17 (base 9) to base 6.Solution: First convert 17 (base 9) to base 10, using the first fast conversion algorithm:1x99+716Next, convert 16 (base 10) to base 6, using the second fast conversion algorithm:6 | 166 | 2+40+2Reading up, 17 (base 9) equals 24 (base 6), which both equal 16 (base 10)Base 8 has a Special Relationship to Base 2Conversion between octal and binary is particularly fast and trivial, if you are careful. Since 23 = 8, every 3 binary digits converts to 1 octal digit, but you have to start in the correct place - the radix pointThe conversion is00000011010201131004101511061117Ex. Convert 10110011001111101000 to octalSolution: starting at the RIGHT, block off into groups of 310|110|011|001|111|101|000Now convert group-by-group to2631750 (octal)Conversion from octal to binary is even easier.Ex. Convert 307125 to binarySolution: 011|000|111|001|010|101, or, removing the dividing bars and the (useless for now) preceding 0, 11000111001010101Hexadecimal to BinaryHex to binary is just as quick and trivial, except, since 16 = 24, the binary numbers are grouped by 4s, and a longer conversion table needs to be rememberedBinaryHexadecimal000000001100102001130100401015011060111710008100191010A1011B1100C1101D1110E1111FEx: Convert 1011010100001110101101010110011 to hexSolution: 101|1010|1000|0111|0101|1010|1011|0011 converts to 5A875AB3 (hex)Ex: Convert ACD01BF to binarySolution: 1010110011010000000110111111Binary Numbers in Real MachinesReal computers have a fixed length space for the storage of positive whole numbers in binary.First question: How do we store numbers that are too short to fit?Solution: Add preceding zeroes.Ex: Show how 5 will be represented in 8 bitsSolution: 101 is only 3 bits long, so add 5 preceding zeroes to obtain 00000101Ex: Show how 5 will be represented in 32 bitsSolution: 00000000000000000000000000000101Second question: What is the largest number you can store this way in a fixed number of bits?Solution: In binary it is all 1s, which is 1 less than 2 to the power of the number of bits!Ex: Whats the largest number that can be stored in 8 bitsSolution: 11111111 = 100000000 - 1 = 255Third question: How many different numbers can be stored in a fixed number of bits?Solution: 2 to the number of bits (all the combinations)Ex: How many values can be stored in 8 bitsSolution: 256Estimating Large Powers of 2Most real computers frequently deal with larger collections of bits than 8. The VAX routinely handles 32 bits at a time (it prefers it to anything shorter), and can handle collections of 64, 128, and, on rare occasion, numbers than occupy 256 bits in length. How many combinations of these numbers are there?Repeatedly multiplying by 2 to get the answer will take a long time - and is a waste of time.Note: 210 = 1024 = 1K 1,000Note: 220 = 210 x 210 = 1024 x 1024 = 1 Meg 1,000,000Note: 230 = 210 x 210 x 210 = 1 Gig 1,000,000,000250 would have 5 commas2120 would have 12 commasNow, all you need to do is get the LEADING DIGITS of the answer by looking at the power of two of the TRAILING DIGIT of the exponentEx: Estimate 236Solution: 64,000,000,000Ex: Estimate 245Solution: 32,000,000,000,000Ex: Estimate 2123Solution: 8,000,000,000,000,000,000,000,000,000,000,000,000Positional Number System for Values Less than 1What does .475 (base 10) represent (in base 10)?4 x 10-14 x .1.47 x 10-27 x .01.075 x 10-35 x .001.005So what does .1101 (base 2) represent (in base 10)?1 x 2-11 x .5.51 x 2-21 x .25.250 x 2-30 x .125.01 x 2-41 x .0625.0625This is a totally unreasonable way of doing this conversion - and there is a way just as fast for fractionals as there is for whole numbersFaster Conversion of Binary Fractions to Decimal(Dibble-Dabble, Horners Method, Extension of Algorithms 1.1 and 1.2)1. Start at the right, start with 02. Add in the digit3. Divide by 24. If there are more digits to the left, (but to the right of the binary point), go back to step 2Ex: .1101 (binary) converted to base 10 is:0+12| 10.5+02|0.50.25+12|1.250.625+12|1.6250.8125Fast Decimal Fraction to Binary Conversion(Horners Method, Dibble-Dabble, Extension of Algorithms 1.1 and 1.2)Use the inverse of the method used for integersNote:- if a number is between 1/2 and 1, then the first binary digit after the binary point is a 1- otherwise , if the number is less than 1/2, the first binary digit is a 0.Note:- if we multiply the decimal number by 2, the whole number we get is the first binary digit after the binary point.Ex: Convert .40625 (decimal) to binary.40625x20.8125x21.625x21.25x20.5x21.0Now, the trick to remember is that the MSB is ON TOP, so read the answer from the top down:.40625(decimal) = .01101 (binary)Accuracy between Binary and DecimalNote that 0.1 (decimal) does not come out evenly when converted to bi