??? 03/03/09 10:01 Read: times |
#163017 - Division is shift and compare Responding to: ???'s previous message |
You may iterate this problem with shift and compare.
Figure out integer part: How many times can you divide 0624h by 0C49? 0, so no subtraction. Now, shift the divisor left one step 0624h <<= 1 = 0C48h Current weight 0.5. How many times can you divide 0C48h by 0C49h? 0, so no subtraction, and no addition of weight. Now, shift the divisor left one step. 0C48h <<= 1 = 1890h Current weight 0.25. How mny times can you divide 1890h with 0C49h? Since you are stepping one bit at a time, the answer will always be 0 or 1. In this case, the number is at least large enough, so the answer is 1. Add current weight 0.25 to your result - now you have 0.25. Subtract divident: 1890h - 0C49h = 0C47h. Now, shift the divisor left one step. 0C47H <<= 1 = 188Eh Current weight 0.125 How many times can you divide 188E with 0C49h. One time, so add 0.125 to your result - now you have 0.375. Subtract dividend and shift left: (188E - 0C49) << 1 gives 188A 188A >= 0C49, so divides 1 time. Current weight was 0.0625, so your current result is 0.375 + 0.0625 gives 0.4375. Subtract and shift: (188A - 0C49) << 1 gives 1882. 1882 >= 0C49, so divides 1 time. Current weight was 0.03125 so 0.4375 + 0.03125 gives 0.46875. Subtract and shift: (1882 - 0C49) << 1 gives 1872. Repeat until the subtract results in zero, or you have enough number of value digits in your answer. When workig with integers, you have to decide how you like your answer. Either scale it with a constant and use fixed point arithmetic, i.e a scaling of 10000 gives: 10000 represets 1. 5000 represents 0.5 1000 represents 0.1 ... The closest you would get to 1 from below would be 9999, representing 0.9999. So you would then add 2500 + 1250 + 625 + .. to form your result. Or you may decide that you want your answer to be a fractions, i.e each 0.5 represented by a bit. Say a 32-bit integer as answer on the format 16.16, i.e. the high 16 bits are integer part, and the low 16 bits are fractional part. The fractional values to add would then be: 32768 represets 0.5 16384 represents 0.25 8192 represets 0.125 4096 represets 0.0625 ... The closest you get to 1 frow below will be 0x0000ffff Note that the first comparison above, computing the integer part, isn't limited to a divisability of 0 or 1. So you may have to do the reverse when finding the integer part - you may have to multiply your dividend (0C49h) by two a number of times until it is about to shift out high-end bits or until it is larger or iqual to the divisor. Or if your processor has a big enough div instruction, you may let the processor compute the integer part of the division. |
Topic | Author | Date |
32 or 16 bit division | 01/01/70 00:00 | |
Suggest 8052.com Code Library | 01/01/70 00:00 | |
Division is shift and compare![]() | 01/01/70 00:00 |