C/C++ で % (モジュラス) を使用する代わりの方法はありますか?

ああ、ビット演算の楽しさ。多くの除算ルーチンの副作用はモジュラスです。そのため、実際には除算がモジュラスよりも速い場合はほとんどありません。あなたがこの情報を入手した情報源を知りたいです。乗算器を備えたプロセッサには、乗算器を使用した興味深い除算ルーチンがありますが、除算の結果からモジュラスまであと 2 つのステップ (乗算と減算) で取得できるため、それでも同等です。プロセッサに除算ルーチンが組み込まれている場合は、剰余も提供されることがわかります。

それでも、剰余演算を最適化する方法を本当に理解したい場合は、研究が必要な剰余算術に特化した数論の小さな分野があります。たとえば、モジュラー演算は、魔方陣を生成するのに非常に便利です。

そのため、x の例のモジュラスの計算を非常に低レベルで見てみましょう。これは、除算と比較していかに単純であるかを示しているはずです:

おそらく、この問題を考えるより良い方法は、基数とモジュロ演算の観点からです。たとえば、目標は DOWmod 7 を計算することです。ここで、DOW は曜日の 16 ビット表現です。これは次のように記述できます:

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

このように表現すると、上位バイトと下位バイトの modulo 7result を個別に計算できます。高値の結果に 4 を掛け、それを低値に加算し、最後にモジュロ 7 で結果を計算します。

8 ビット数の 7 を法とする結果の計算も、同様の方法で実行できます。次のように 8 ビットの数値を 8 進数で書くことができます:

  X = a*64 + b*8 + c

ここで、a、b、および c は 3 ビットの数値です。

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

64%7 = 8%7 = 1以降

もちろん、a、b、c は

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

a+b+c の可能な最大値 7+7+3 = 17 です .したがって、8 進ステップがもう 1 つ必要になります。完全な (テストされていない) C バージョンは次のように記述できます:

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

PIC バージョンの作成に少し時間を費やしました。実際の実装は上記とは少し異なります

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

これは、アルゴリズムをテストするための小さなルーチンです

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

最後に、16 ビットの結果 (私はテストしていません) の場合、次のように書くことができます:

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

スコット


数値 mod 2 の累乗を計算する場合は、ビットごとの and 演算子を使用できます。 2 番目の数値から 1 を引くだけです。例:

x % 8 == x & 7
x % 256 == x & 255

いくつかの注意事項:

<オール>
  • これはのみ機能します 2 番目の数値が 2 の累乗の場合
  • モジュラスが常に正の場合にのみ同等です。 C および C++ 標準では、最初の数値が負の場合のモジュラスの符号を指定していません (C++11 までは 指定 負であることを保証します。これは、ほとんどのコンパイラがすでに行っていたことです)。ビット単位で符号ビットを取り除くため、常に正になります (つまり、剰余ではなく、真のモジュラスです)。とにかくそれがあなたの望みのようですね。
  • コンパイラは、可能な場合はすでにこれを行っている可能性があるため、ほとんどの場合、手動で行う価値はありません。

  • ほとんどの場合、2 の累乗ではないモジュロを使用するとオーバーヘッドが発生します。これはプロセッサに関係なく (私の知る限り)、モジュラス演算子を使用するプロセッサでさえ、マスク操作とは対照的に除算のほうが数サイクル遅くなります。

    ほとんどの場合、これは考慮に値する最適化ではなく、独自のショートカット操作を計算する価値がないことは確かです (特に、それでも除算または乗算が含まれる場合)。

    ただし、経験則の 1 つは、配列サイズなどを 2 の累乗になるように選択することです。

    したがって、曜日を計算する場合は、約 100 エントリの循環バッファを設定する場合でも、%7 を使用することをお勧めします... 128 にしない理由はありません。その後、% 128 と書くことができ、ほとんどの (すべての) コンパイラはこれを &0x7F<にします。 /P>