C语言 按位运算符的幂 2 的模数？

Mod of power 2 on bitwise operators?

提问by Zo Has

1. How does mod of power of 2 work on only lower order bits of a binary number (1011000111011010)?
2. What is this number mod 2 to power 0, 2 to power 4?
3. What does power of 2 have to do with the modulo operator? Does it hold a special property?
4. Can someone give me an example?

1. 2 的幂模如何仅对二进制数 ( 1011000111011010) 的低位起作用？
2. 这个数字是 2 的 0 次方，2 的 4 次方吗？
3. 2 的幂与模运算符有什么关系？它拥有特殊属性吗？
4. 有人可以举个例子吗？

The instructor says "When you take something mod to power of 2 you just take its lower order bits". I was too afraid to ask what he meant =)

教练说“当你把某个东西取到 2 的幂时，你只需要取它的低阶位”。我太害怕问他是什么意思了 =)

回答by BlueRaja - Danny Pflughoeft

He meant that taking number mod 2^nis equivalent to stripping off all but the nlowest-order (right-most)bits of number.

他的意思是服用number mod 2^n相当于剥离所有，但n最低阶（最右侧）位number。

For example, if n == 2,

例如，如果 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.

So in other words, number mod 4is the same as number & 00000011(where &means bitwise-and)

所以换句话说，number mod 4与number & 00000011（其中&表示按位与）相同

---

---

Note that this works exactly the same in base-10: number mod 10gives you the last digit of the number in base-10, number mod 100gives you the last two digits, etc.

请注意，这在以 10number mod 10为基数的情况下完全相同：为您提供以10为基数的 数字的最后一位数字，number mod 100为您提供最后两位数字等。

回答by user703016

What he means is that :

他的意思是：

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

When y is a power of 2.

当 y 是 2 的幂时。

Example:

例子：

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

Using your example now :

现在使用您的示例：

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

1011000111011010 (45530) modulo
0000000000010000 (2 power 4) =
0000000000001010 (10)
^^^^^^^^^^^^<- ignore these bits

回答by Brian

Consider when you take a number modulo 10. If you do that, you just get the last digit of the number.

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

  334 % 10 = 4
  12345 % 10 = 5

Likewise if you take a number modulo 100, you just get the last two digits.

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

  334 % 100 = 34
  12345 % 100 = 45

So you can get the modulo of a power of two by looking at its last digits in binary. That's the same as doing a bitwise and.

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

回答by Antti

Modulo in general returns the remainder of a value after division. So x mod 4, for example, returns 0, 1, 2 or 3 depending on x. These possible values can be represented using two bits in binary (00, 01, 10, 11) - another way to do x mod 4is to simply set all the bits to zero in x except the last two ones.

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

Example:

例子：

      x = 10101010110101110
x mod 4 = 00000000000000010

回答by Liudvikas Bukys

Answering your specific questions:

回答您的具体问题：

1. mod is a remainder operator. If applied to a series of numbers x in 0, 1, ..., then x mod n will be 0, 1, ..., n-1, 0, 1, ..., n-1, ad infinitum. When your modulus n is a power of 2, then x mod n will count up in binary from 0 to n-1, back to 0, to n-1, etc; for modulus n that looks like binary 01xxxxx, x mod n will cycle through every of those low-order bits xxxxx.
2. binary 1011000111011010 mod 1 is 0 (mod 2^0 yields the last zero bits; everything mod 1 is zero). binary 1011000111011010 mod binary 10000 is 1010 (mod 2^4 yields the last four bits).
3. Division and remainder of binary number by powers of two is particularly efficient because it's just shifting and masking; mathematically it's nothing special.
4. Example: See answer to question 2.

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. 二进制数的除法和余数除以 2 的幂特别有效，因为它只是移位和掩码；从数学上讲，这没什么特别的。
4. 示例：参见问题 2 的答案。