ああ、ビット演算の楽しさ。多くの除算ルーチンの副作用はモジュラスです。そのため、実際には除算がモジュラスよりも速い場合はほとんどありません。あなたがこの情報を入手した情報源を知りたいです。乗算器を備えたプロセッサには、乗算器を使用した興味深い除算ルーチンがありますが、除算の結果からモジュラスまであと 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 の累乗ではないモジュロを使用するとオーバーヘッドが発生します。これはプロセッサに関係なく (私の知る限り)、モジュラス演算子を使用するプロセッサでさえ、マスク操作とは対照的に除算のほうが数サイクル遅くなります。
ほとんどの場合、これは考慮に値する最適化ではなく、独自のショートカット操作を計算する価値がないことは確かです (特に、それでも除算または乗算が含まれる場合)。
ただし、経験則の 1 つは、配列サイズなどを 2 の累乗になるように選択することです。
したがって、曜日を計算する場合は、約 100 エントリの循環バッファを設定する場合でも、%7 を使用することをお勧めします... 128 にしない理由はありません。その後、% 128 と書くことができ、ほとんどの (すべての) コンパイラはこれを &0x7F<にします。 /P>