なぜ（xと3）が（x mod 4）と同じですか？

Question

私は、作者が%演算子の代わりにビット単位で&演算子を使用していると思われるサンプルソースコードをいくつか見つけました。しかし、私がx & 4を試したとき、それはx % 5と同じ値を生成しません。これは、唯一x >= 0に当てはまることに依存してもよいことも

x AND (2^n - 1) 

注

x MOD 2^n 

と等価である：

Answer 1

これは一般的に2

の力のために働きますx < 0のMODの定義。この作業の理由を理解することが

---

は、MODが本当に何であるかを検討 - それは整数の除算を実行した後だけ残りです。 2^nによる除算の場合、バイナリ値をnビットだけ右シフトし、シフトアウトされる任意の下位ビットを破棄する。残り（g hが）の結果として捨ててきた

0 0 a b c d e f 

：我々は^ 2 4 = 2で割る場合は8ビットのバイナリ数

a b c d e f g h 

ために、我々は、2ビット右シフト整数除算。

我々は、我々がちょうど0 0 0 0 0 0 1 1のマスクを適用することによって、ビットをg hを抽出することができ、残りを知りたい場合は、次の一般的な場合にはわずか2である値3を有し有すること

a b c d e f g h 
AND 0 0 0 0 0 0 1 1 
    = 0 0 0 0 0 0 g h 

注^ n - 1

実数で試してみましょう。私たちは4分の42を計算し、商と剰余の両方を取得したいとします

42 = 0 0 1 0 1 0 1 0 

我々は2ビット右シフトした商を取得するには：

42/4 (decimal) 
= 0 0 1 0 1 0 1 0 >> 2 
= 0 0 0 0 1 0 1 0 
= 10 (decimal) 

    42 MOD 4 (decimal) 
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1 
= 0 0 0 0 0 0 1 0 
= 2 (decimal) 

だから、4分の42 = 10余り2

Answer 2

答えは非常に単純ですが、バイナリで考えるようにしてください。

0000 = 0 AND 11 = 0000 = 0 
0001 = 1 AND 11 = 0001 = 1 
0010 = 2 AND 11 = 0010 = 2 
0011 = 3 AND 11 = 0011 = 3 
0100 = 4 AND 11 = 0000 = 0 
0101 = 5 AND 11 = 0001 = 1 
0110 = 6 AND 11 = 0010 = 2 
0111 = 7 AND 11 = 0011 = 3 

...など。

これはリマインダと同じ結果を示します（％は剰余、正式ではモジュラスではありません）。 これは2の累乗でのみ機能し、ゼロと正の数に対してのみ機能します。