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.)
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.)