[dhosek]

Oh definitely. Some of this goes back to my 6502 assembly days when there was no hardware multiply instruction. So to multiply by 40, for example. I would shift right 3 bits, store the result, shift right 2 more bits and add the stored result.

Similarly, a fast divisibility test (we’ll assume we’re dividing n by some odd prime p):

1. Shift the bits of p right so that there is a 1 in the last position.

2. If n = p then p∣n, if n < p then p∤n, otherwise continue.

3. Subtract p and go back to step 1.

(One of my ADD habits during meetings is to find the prime factors phone numbers or anything else very long. I do something similar with the numbers in decimal, but for this, I’ll subtract multiples of the potential divisor to get 0s at the end of the number in decimal. I remember co-workers puzzling over a piece of paper with my notes I left behind in a conference room trying to figure out what the numbers represented and how the process worked.)

[unwind]

Left, you would (obviously, this is a typo) shift left. And 3 followed by 2 since 1<<3 is 8, and 1<<5 is 32 and 8+32 is 40.