c++ - 使用移位运算符除以任意数

Question

n例如，如何24使用移位运算符和加法来划分一个数字？

( n % 24 == 0)

Answer 1

除法的铅笔和纸算法仅使用“移位”（以 10 为底的移位）和减法。你可以在 base 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 毫无疑问是一个聪明的 hack，但使用移位运算符 [和/或减法] 仅对 2 的幂才真正有意义。即便如此，与使用现代代码生成更高效的代码相比，它更容易让读者感到困惑编译器。