45
  1. 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 为底的情况下完全相同： number mod 10为您提供以 10 为底的数字的最后一位，number mod 100为您提供最后两位等。

于 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 的数字，你只会得到最后两位数。

  334 % 100 = 34
  12345 % 100 = 45

因此，您可以通过查看二进制的最后一位数字来获得 2 的幂的模数。这与按位与相同。

于 2011-07-12T20:35:31.580 回答
5

Modulo 通常返回除法后的余数。因此x mod 4，例如，根据 x 返回 0、1、2 或 3。这些可能的值可以使用二进制 (00, 01, 10, 11) 中的两位表示 - 另一种方法x mod 4是简单地将 x 中的所有位设置为零，除了最后两位。

例子：

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

回答您的具体问题：

  1. mod 是余数运算符。如果应用于 0, 1, ... 中的一系列数字 x，则 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 都为零）。binary 1011000111011010 mod binary 10000 是 1010（mod 2^4 产生最后四位）。
  3. 二进制数除以二的幂的余数特别有效，因为它只是移位和屏蔽；从数学上讲，这没什么特别的。
  4. 示例：参见问题 2 的答案。
于 2011-07-12T20:45:42.760 回答