30

特定の基数に対して、標準の % 演算子よりも高速な整数モジュラスを作成するためのトリックはありますか?

私のプログラムでは、約 1000 ～ 4000 を探します (例: n%2048)。単純に n モジュラス 2048 を実行するよりも簡単な方法はありn%2048ますか?

4

7 に答える 7

45

2048 の例のように、コンパイル時に分母が 2 のべき乗であることがわかっている場合は、1 を減算してビットごとの AND を実行できます。

あれは：

n % m == n & (m - 1)

...mは 2 のべき乗です。

例えば：

22 % 8 == 22 - 16 == 6

         Dec   Bin
       -----   -----
          22 = 10110
           8 = 01000  
       8 - 1 = 00111 
22 & (8 - 1) =   10110 
               & 00111 
               -------
           6 =   00110

優れたコンパイラには独自の最適化機能が%あり、おそらく上記の手法と同じくらい高速であることに注意してください。算術演算子は、かなり高度に最適化される傾向があります。

于 2012-06-14T20:16:13.257 に答える
15

2 の累乗の2^n場合、最後のビットを除くすべてのビットをゼロにするだけですn。

例 (32 ビット整数を想定):

x%2と同等ですx & 0x00000001

x%4と同等ですx & 0x00000003

一般x % (2^n)に に等しいx & (2^n-1)。C で書くと、これはx & ((1<<n)-1).

これは、(右から) 番目のビット2^nに 1 が返されるためです。n+1したがって、右側に 1、左側に 0 が表示されます2^n-1。n

于 2012-06-14T20:14:25.897 に答える
2

モジュラス演算を再現するいくつかの手法を次に示します。

ベンチマークされたものの中で、これが最速でした (2048 年のシナリオに合わせて変更されています)。あなたの「最大」が数百万ではなく、あなたが言及した1000-4000の範囲である限り、あなたにとってもより速く動作するかもしれません:

int threshold = 2048; //the number to mod by
int max = 1000; //the number on the left. Ex: 1000 % 2048
int total = 0;
int y = 0;
for (int x = 0; x < max; x++)
{
    if (y > (threshold - 1))
    {
        y = 0;
        total += x;
    }
    y += 1;
}
return total;

試してごらん。さまざまな設定で著者のマシンでより高速に実行されたので、あなたにとっても見事に実行されるはずです.

于 2014-10-15T07:58:44.913 に答える
2

つまり、上位ビットをゼロにすることができます

x = 11 = 1011
x % 4 = 3 = 0011

したがって、 x % 4 の場合、最後の 2 ビットを取得するだけで済みます。ただし、負の数を使用するとどうなるかはわかりません。

于 2012-06-14T20:13:58.840 に答える
0

符号なし整数を乗算/除算する最速の方法は、左または右にビット シフトすることです。シフト操作は、CPU コマンドに直接一致します。たとえば、3 << 2 = 6 で、4>>1 = 2 です。

モジュールを計算するために同じトリックを使用できます。残りのビットのみが残るように整数を十分に左にシフトし、次に右にシフトして剰余の値を確認できるようにします。

一方、整数モジュロも CPU コマンドとして存在します。最適化されたビルドで整数モジュロ演算子がこのコマンドにマップされている場合、ビット シフト トリックを使用しても改善は見られません。

次のコードは、最後の 2 ビットだけが残るように十分にシフトすることによって 7%4 を計算します (4=2^2 であるため)。これは、30 ビットをシフトする必要があることを意味します。

uint i=7;
var modulo=((i<<30)>>30);

結果は 3

編集：

上位ビットを単純に消去することを提案しているすべてのソリューションを読んだだけです。同じ効果がありますが、はるかに単純で直接的です。

于 2012-06-14T20:20:23.613 に答える
0

2 の累乗であるリテラルで除算する場合、答えはおそらくノーです。適切なコンパイラは、そのような式を自動的に AND 演算のバリエーションに変換します。これは最適にかなり近いものです。

于 2012-06-14T20:51:40.047 に答える