45
  1. 2 の累乗の mod は、2 進数 ( ) の下位ビットのみでどのように機能し1011000111011010ますか?
  2. この数 mod 2 の 0 乗、2 の 4 乗は何ですか?
  3. モジュロ演算子と 2 のべき乗は何の関係がありますか? 特別な性質を持っていますか？
  4. 誰かが私に例を挙げてもらえますか?

インストラクターは、「mod を 2 の累乗にするときは、下位ビットだけを使用する」と言っています。私は彼が何を意味するのかを尋ねるのが怖すぎた =)

4

5 に答える 5

72

彼は、取ることが、の最下位（右端）のビットをnumber mod 2^n除くすべてを取り除くことと同等であることを意味しました。nnumber

たとえば、n==2の場合

number      number mod 4
00000001      00000001
00000010      00000010
00000011      00000011
00000100      00000000
00000101      00000001
00000110      00000010
00000111      00000011
00001000      00000000
00001001      00000001
etc.

つまり、は（ビット単位の意味）とnumber mod 4同じです-そして）number & 00000011&

これは基数10でもまったく同じように機能することに注意してください。基数10 number mod 10の数値の最後の桁をnumber mod 100示し、最後の2桁を示します。

于 2011-07-12T20:40:16.030 に答える
41

彼が意味することは次のとおりです。

x modulo y = (x & (y − 1))

y が 2 の累乗の場合。

例：

0110010110 (406) modulo
0001000000 (64)  =
0000010110 (22)
^^^^<- ignore these bits

今あなたの例を使用してください：

1011000111011010 (45530) modulo
0000000000000001 (2 power 0) =
0000000000000000 (0)
^^^^^^^^^^^^^^^^<- ignore these bits

1011000111011010 (45530) modulo
0000000000010000 (2 power 4) =
0000000000001010 (10)
^^^^^^^^^^^^<- ignore these bits
于 2011-07-12T20:34:42.643 に答える
13

モジュロ 10 の数値を取る場合を考えてみましょう。これを行うと、数値の最後の桁が得られます。

  334 % 10 = 4
  12345 % 10 = 5

同様に、数値を 100 で割ると、最後の 2 桁だけが得られます。

  334 % 100 = 34
  12345 % 100 = 45

したがって、バイナリの最後の桁を見ることで、2 のべき乗のモジュロを取得できます。これは、ビット単位の and を実行するのと同じです。

于 2011-07-12T20:35:31.580 に答える
5

モジュロは一般に、除算後に値の余りを返します。したがってx mod 4、たとえば、xに応じて0、1、2、または3を返します。これらの可能な値は、バイナリ（00、01、10、11）の2ビットを使用して表すことができます。別の方法x mod 4は、最後の2ビットを除くすべてのビットをxでゼロに設定することです。

例：

      x = 10101010110101110
x mod 4 = 00000000000000010
于 2011-07-12T20:38:54.847 に答える
3

特定の質問に答える:

  1. mod は剰余演算子です。一連の数値 x に 0、1、... を適用すると、x mod n は 0、1、...、n-1、0、1、...、n-1 と無限になります。モジュラス n が 2 の累乗の場合、x mod n はバイナリで 0 から n-1 にカウントアップし、0 に戻り、n-1 にカウントアップします。バイナリ 01xxxxx のように見えるモジュラス n の場合、x mod n はそれらの下位ビット xxxxx のすべてを循環します。
  2. バイナリ 1011000111011010 mod 1 は 0 です (mod 2^0 は最後のゼロ ビットを生成します。mod 1 はすべてゼロです)。バイナリ 1011000111011010 mod バイナリ 10000 は 1010 です (mod 2^4 は最後の 4 ビットを生成します)。
  3. 2 の累乗による 2 進数の除算と剰余は、シフトとマスキングだけであるため、特に効率的です。数学的には特別なことではありません。
  4. 例: 質問 2 の回答を参照してください。
于 2011-07-12T20:45:42.760 に答える