位运算中的2次幂模运算？

Question

1. 如何对二进制数(1011000111011010)的低位进行2次幂取模？
2. 对于0次方和4次方，这个数字的模是多少？
3. 2的幂与模运算有什么关系？它是否具有特殊属性？
4. 能否给出一个例子？

教练说：“当你对2的幂取模时，只需要取它的低位”。我太害怕问他是什么意思了=）

- Zo Has

---

为什么不试着手工计算一些示例，然后你就会看到会发生什么。 - starblue

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（其中的 & 表示按位与）。

---

请注意，在十进制中也是完全相同的： number mod 10 可以得到数字在十进制下的个位数，number mod 100可以得到数字在十进制下的最后两位数，等等。

- BlueRaja - Danny Pflughoeft

---

只有所有操作数都是正数时才成立！根据编程语言的不同，行为也会有所不同。例如，在C语言中，即使在代数中我们通常期望“-5 mod 4”为3，但“-5 % 4 == -1”。这意味着，如果左操作数不是无符号数，编译器将不会优化带有“％4”的文字并使用“&”运算符。 - calandoa

@calandoa：我们在这里讨论的是二进制作为一种数字系统，而不是数字的位编码。例如，-5写作-101。 - BlueRaja - Danny Pflughoeft

@BlueRaja：当然，我们正在谈论位编码：&未定义数学运算符-。我猜你的意思更多的是“我们不讨论负数”。也许我们确实没有讨论，但这在问题和你的回答中并不清楚，所以我做了澄清。 - calandoa

你认为像 number MOD 256 <=> (number & (0xFF00)) >> 8 这样的东西怎么样？（其中2^8 = 256） - Sandburg

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

- user703016

Answer 3

当你对一个数取模10时，你得到的就是这个数的个位数。

  334 % 10 = 4
  12345 % 10 = 5

如果你对一个数取模100，你就得到了它的最后两位数字。

  334 % 100 = 34
  12345 % 100 = 45

你可以通过查看二进制的最后几位来获取一个二的幂次方的模数。这与执行按位与操作相同。

- Brian

---

这也适用于2的幂次方吗？54％32，即2的5次方为22。 - Zo Has

Popo：是的。结尾处的比特数取决于你使用的二的幂次方。正如Cicada所描述的那样，你可以将其计算为54 & (32-1)。 - Brian

Answer 4

模运算通常返回除法后的余数。例如，x mod 4 返回0、1、2或3，具体取决于x的值。这些可能的值可以用二进制的两位（00、01、10、11）表示——另一种做法是将x中除最后两位外的所有位都设置为零来进行x mod 4。

示例：

      x = 10101010110101110
x mod 4 = 00000000000000010

- Antti

Answer 5

回答您具体的问题：

1. mod是一个取余运算符。如果应用于一系列数字x在0、1、…中，那么x mod n将是0、1、…、n-1、0、1、…、n-1、无限循环。当你的模数n是2的幂时，x mod n将从0到n-1按二进制计数，然后再从n-1回到0，以n-1，等等;对于长这样的二进制01xxxxx的模数n，x mod n将循环通过每个低位比特xxxxx。
2. 二进制1011000111011010 mod 1是0（mod 2^0得到最后的零位；任何数对1取模都是零）。二进制1011000111011010 mod二进制10000是1010（mod 2^4得到最后的四个位）。
3. 二进制数除以2的幂的商和余数非常高效，因为它只是移位和屏蔽；从数学上讲，它并不特别。
4. 示例：请参见问题2的答案。

- Liudvikas Bukys