Path: EDN Asia >> Design Ideas >> IC/Board/Systems Design >> Bit-shifting method for fast integer multiplication
IC/Board/Systems Design Share print

Bit-shifting method for fast integer multiplication

21 Mar 2016  | Aaron Lager

Share this page with your friends

This design idea introduces 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: 12x12=144→(4+8)x12=144→(12x4)+(12x8)=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: 6x10=60→(2+4)x10=60→(2x10)+(4x10)=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.5x10=25→(2+0.5)x10=25→(2x10)+(0.5x10)=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.125x80=250→(2+1+0.125)x80=250→(2x80)+(1x80)+(0.125x80)=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.625x80=210→(2+0.5+0.125)x80=210→(2x80)+(0.5x80)+(0.125x80)=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 8x8-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)).


About the author
Aaron Lager contributed this article.


This article is a Design Idea selected for re-publication by the editors. It was first published on May 29, 2008 in EDN.com.




Want to more of this to be delivered to you for FREE?

Subscribe to EDN Asia alerts and receive the latest design ideas and product news in your inbox.

Got to make sure you're not a robot. Please enter the code displayed on the right.

Time to activate your subscription - it's easy!

We have sent an activate request to your registerd e-email. Simply click on the link to activate your subscription.

We're doing this to protect your privacy and ensure you successfully receive your e-mail alerts.


Add New Comment
Visitor (To avoid code verification, simply login or register with us. It is fast and free!)
*Verify code:
Tech Impact

Regional Roundup
Control this smart glass with the blink of an eye
K-Glass 2 detects users' eye movements to point the cursor to recognise computer icons or objects in the Internet, and uses winks for commands. The researchers call this interface the "i-Mouse."

GlobalFoundries extends grants to Singapore students
ARM, Tencent Games team up to improve mobile gaming


News | Products | Design Features | Regional Roundup | Tech Impact