按位运算符的 2 次方取模？

Question

1. 2 的幂模如何仅适用于二进制数的低位 (1011000111011010)？
2. 这个数 mod 2 的 0 次方、2 的 4 次方是多少？
3. 2 的幂与模运算符有什么关系？它是否拥有特殊属性？
4. 有人能给我举个例子吗？

老师说“当你取某个东西的 2 次方时，你只需取它的低位”。我太害怕了，不敢问他的意思 =)

Answer 1

他的意思是，采用number mod 2^n相当于剥离n最低阶（最右边）位之外的所有<代码>数字。

例如，如果 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 给出最后两位数字，等等。

Answer 2

他的意思是：

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

Answer 3

考虑一下当您对一个数字取模 10 时。如果您这样做，您只会得到该数字的最后一位数字。

  334 % 10 = 4
  12345 % 10 = 5

同样，如果你对一个数字取模 100，你只得到最后两位数字。

  334 % 100 = 34
  12345 % 100 = 45

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

Answer 4

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

例子：

      x = 10101010110101110
x mod 4 = 00000000000000010

Answer 5

回答您的具体问题：

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 都为零）。二进制 1011000111011010 mod 二进制 10000 为 1010（mod 2^4 产生最后四位）。
3. 二进制数除以 2 的幂特别有效，因为它只是移位和掩码；从数学上来说，这没什么特别的。
4. 示例：参见问题 2 的回答。