シフト演算子を使用して任意の数で除算する

Question

シフト演算子と加算を使用して、たとえば 24 で数値 n を除算するにはどうすればよいですか？

（ n％24 == 0 ）

Answer 1

これは、最初に結果の最上位ビットを見つけ、次に戻ることで機能します。

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 2

部門の鉛筆と紙のアルゴリズムは、「シフト」のみを使用します。 （ベース10シフト）および減算。ベース2でもまったく同じことができます。

申し訳ありませんが、アルゴリズムのリンクは見つかりませんが、子供の頃に学習したはずです。

編集：実際には追加は安価であるため、正しい数字を1つずつ抽出する必要はないため、アルゴリズムを少し簡略化できます...

正の配当と除数を仮定...

除数よりもすぐに大きい2のべき乗（ここでは32）を取ります。

この2の累乗で数字を簡単に除算できます。部門が k1 を生成するとします。 番号から k1 * 24 を引き（残りの r1 を呼び出し）、繰り返します...

k1 、 k2 、... kn の数字と残りの rn を取得したとき32が含まれています。最後のチェックを実行して、 rn に24が含まれているかどうかを確認します。

除算の結果は、 k1 + k2 + ... + kn（24がrnに収まる場合は+1）です。

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最新のコンパイラで。