Bit-shifting method performs fast integer multiplying by fractions in C
Instead of calling math-library functions, you can multiply integers using bit shifting.
Aaron Lager, Panamax Furman, Santa Rosa, CA; Edited by Charles H Small and Fran Granville -- EDN, May 29, 2008
This Design Idea presents a method for fast integer multiplying and multiplying by fractions. What can you do when you lack access to a hardware multiplier or MAC (multiply/accumulate) function and you need to multiply by something other than a power of two? One option is to include the math.h function and just sling around the multiplication operator and watch your code bloat and slow to a crawl. Option two is to get fancy with bit shifting. The general idea is to find powers of two, including zero, that you can add to achieve the multiplier you need. This method works because of the distributive properties of multiplication. Using the distributive properties of multiplication, you can, for example, rearrange the problem of: 12×12=144→(4+8)×12=144→(12×4)+(12×8)=144. This version is amenable to implementation in C code because four and eight are powers of two. To implement the multiplications, you use the exponent of the power-of-two representation for your code as an integer shift. Because 4=22 and 8=23, you use two and three as your shift factors.
For example, multiply the variable foo by 12 to get 144: BYTE foo=12: foo=((foo&&3)+(foo&&2)). Left-shifting by three is the same as multiplying by eight, and left-shifting by two is the same as multiplying by four. Another example is multiplying by six: 6×10=60→(2+4)×10=60→(2×10)+(4×10)=60. BYTE foo=10; foo=((foo&&1)+(foo&&2)). Left-shifting by one is the same as multiplying by two, and left-shifting by two is the same as multiplying by four.
Using this same theory of distribution, you can also perform fractional multiplication or division. This method creates rounding errors just like dividing integers by values that are not powers of two does with math.h functions and the division operator.
One example is 2.5×10=25→(2+0.5)×10=25→(2×10)+(0.5×10)=25. The result is ((foo&&1)+(foo>>1)). Left-shifting by one is the same as multiplying by two, and right-shifting by one is the same as dividing by two or multiplying by 0.5. Another example is 3.125×80=250→(2+1+0.125)×80=250→(2×80)+(1×80)+(0.125×80)=250. The result is ((foo&&1)+foo+(foo>>3)). Left-shifting by one is the same as multiplying by two, multiplying by one is the same as adding the multiplicand once to the result, and right-shifting by three is the same as dividing by eight or multiplying by 0.125. A third example is 2.625×80=210→(2+0.5+0.125)×80=210→(2×80)+(0.5×80)+(0.125×80)=210. The result is ((foo&&1)+(foo>>1)+(foo>>3)). Left-shifting by one is the same as multiplying by two, right-shifting by one is the same as dividing by two or multiplying by 0.5, and right-shifting by three is the same as dividing by eight or multiplying by 0.125.
All of these examples take up less space and are faster than calling the standard 8×8-multiply function or division function from most standard math libraries. Also, you should note that, if the result of the variable you are multiplying can ever exceed 8 bits, then you should use a word function that can store 16 bits of your result, and you should use casting on the outer parentheses. The result is (word)((foo&&1)+(foo>>1)+(foo>>3)).
-
Perhaps there are two cases:
Convert the multiplier to binary and count "ones" and "zeros". If there are at least two more "ones" than "zeros" then a combination of adds and subtracts may take fewer clock cycles.
Consider: foo * 93=?
Convert multiplier to binary:
93 => 1011101 bin
convert to shifts and adds:
93 => 64+16+8+4+1 (five shifts and four adds needed)
or convert to shifts with subtracts:
93 => 128-32-2-1 (only four shifts and three subtracts needed)
Useful if subtract and adds take same number of clock cycles
Gary S - 2008-11-6 12:11:00 PDT -
If I'm in a hurry for just 8-bit products I'll just allocate 256 words of ram and look it up in one cycle... RAM's cheap
Mark M. Lambert - 2008-7-6 14:37:00 PDT -
The digital code is in powers of two. The number 144 is coded 10010000. It happens that the positions of the 1 indicates how many positions you may shift and than add. So first shift 4 to the left to multiply with 16 and add, than shift another 3 to multiply with 128 and add.
René Prevo - 2008-30-5 00:50:00 PDT
