Dividing by arbitrary numbers using shifting operators

Question

How can you divide a number n for example by 24 using shifting operators and additions?

(n % 24 == 0)

Answer 1

While there is no doubt a clever hack for 24, using shift operators [and/or subtractions] only really makes sense for powers of 2. Even then, its far more likely to confuse readers than it is to generate more efficient code with a modern compiler.

Answer 2

The pencil-and-paper algorithm for the division uses only "shifts" (base 10 shifts) and subtractions. You can do exactly the same thing in base 2.

Sorry I can't find a link for the algorithm, but you should have learnt it as a child.

EDIT: actually since additions are cheap, you don't have to try to extract the correct digits one by one, so you can simplify the algorithm a bit...

Assuming positive dividend and divisor...

Take the power of two immediately larger than the divisor (here, 32).

It is easy to divide your number by this power of two. Say the division produces k1. Subtract k1*24 from the number (call the rest r1) and iterate...

When you have obtained k1, k2, ... kn numbers and the rest rn no longer contains 32, do a last check to see if rn contains 24.

The result of the division is k1+k2+...+kn (+1 if 24 fits in rn).

Answer 3

int
div24(int value) {
   int result = 0;
   while (value >= 24) {       
      int accum = 24;
      int tmp = 1;   
      while (accum + accum <= value) {
         accum += accum;
      tmp += tmp;
      }
      value -= accum;   
      result += tmp;
   }   
   return result;
}

Answer 4

This works by first finding the highest bit of the result, and then working back.

int div24(int value) {
  // Find the smallest value of n such that (24<<n) > value
  int tmp = 24;
  for (int n = 0; tmp < value; ++n)
    tmp <<= 1;
  // Now start working backwards to find bits of the result. This is O(i).
  int result = 0;
  while(value != 0) {
    tmp >>= 1;
    result <<= 1;
    if (value > tmp) { // Found one bit.
       value -= tmp; // Subtract (24<<i)
       result++;
    }
  }
  return result;
}

Example:

Value = 120 :  n = 2
Step 0: tmp = 96, result = 0, value = 24, result = 1
Step 1: tmp = 48, result = 2
Step 2: tmp = 24, result = 4, value = 0, result = 5