On small CPUs, you often don’t have a multiply or divide instruction. Of course, good programmers know that shifting right and left will multiply or divide by a power of two. But there are always cases where you need to use something that isn’t a power of two. Sometimes you can work it out for multiplication.
For example, multiplying by 10 is common when dealing with conversion between binary and decimal. But since 10n is equal to 8n+2n, you can express that as a bunch of left shift three times to multiply by eight, adding that value to your original value shifted left once to multiply by two.
But division is a different problem. n/10 does not equal n/8-n/2 or anything else simple like that. The other day a friend showed me a very convoluted snippet of code on Stack Overflow by user [realtime] that divides a number by 10 and wanted to know how it worked. It is pretty straightforward if you just stick with the math and I’ll show you what I mean in this post. Turns out the post referenced the venerable Hacker’s Delight book, which has a wealth of little tricks like this.
First Multiply
First, let’s do some shifts to multiply. Each left shift is a power of two, so n 2); q = q + (q >> 4); q = q + (q >> 8); q = q + (q >> 16); q = q >> 3; r = n - (((q >1)+(n>>2)
This is really n/2 + n/4. If you remember your high school math, that’s the same as 3n/4. Of course, this is the same as multiplying by 0.75. If you look ahead to the last assignment of q, you’ll get a clue:q=q>>3;
Support the originator by clicking the read the rest link below.
