c++ - シフト演算子を使用した任意の数値による除算

Question

nたとえば、24シフト演算子と足し算を使用して、数値をどのように除算できますか?

( n % 24 == 0)

Answer 1

除算のための鉛筆と紙のアルゴリズムは、「シフト」(基数 10 のシフト) と減算のみを使用します。ベース2でもまったく同じことができます。

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

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

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

除数 (ここでは 32) のすぐ大きい 2 のべき乗をとります。

この 2 の累乗で数を割り算するのは簡単です。除算が生成するとし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 の累乗に対してのみ意味があります。コンパイラ。