Деление на произвольные числа с помощью операторов сдвига

Question

Как можно разделить число n, например, на 24, используя операторы сдвига и дополнения?

(n % 24 == 0)

Answer 1

Алгоритм карандашного и бумажного деления использует только «сдвиги» (основа 10 сдвигов) и вычитания. Вы можете сделать то же самое в базе 2.

Извините, я не могу найти ссылку для алгоритма, но вы должны были выучить ее в детстве.

РЕДАКТИРОВАТЬ: фактически, поскольку добавления дешевы, вам не нужно пытаться извлечь правильные цифры одну за другой, так что вы можете немного упростить алгоритм ...

Принятие положительных дивидендов и делителей ...

Возьмите степень двойки сразу больше, чем делитель (здесь, 32).

Легко разделить ваше число на эту степень двойки. Скажем, дивизия производит k1. Вычтите k1*24 из числа (позвоните остальным r1) и итерируйте ...

Когда вы получили номера k1, k2, ... kn, а остальные rn больше не содержат 32, выполните последнюю проверку, чтобы убедиться, что rn содержит 24.

Результат деления k1+k2+...+kn (+1 if 24 fits in rn).

Answer 2

Это работает, сначала находя старший бит результата, а затем возвращаясь.

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;
}

Пример:

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

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

Несмотря на то, что нет сомнений в умном взломе 24, использование операторов сдвига [и / или вычитаний] действительно имеет смысл только для степеней 2. Даже в этом случае вероятность того, что читатель может сбить с толку гораздо больше, чем генерировать более эффективный код с современным компилятором.