为什么(x&3)与(x mod 4)相同？

Question

我找到了一些示例源代码,其中作者似乎使用按位运算&符而不是%运算符.但是,当我尝试x & 4它时,它不会产生相同的值x % 5.

Answer 1

这仅适用于2的幂.

一般来说:

x MOD 2^n

相当于:

x AND (2^n - 1)

另请注意,这可能仅适用于x >= 0,具体取决于您对MODfor 的定义x < 0.

要理解为什么这个工程,考虑什么MOD真的是-它只是剩余执行整数除法后.在除以2 ^ n的情况下,我们实际上只是将二进制值右移n位并丢弃任何移出的低阶位,例如对于8位二进制数

a b c d e f g h

如果我们除以4 = 2 ^ 2那么我们向右移2位:

0 0 a b c d e f

g h由于整数除法,余数()已被丢弃.

如果我们想知道余数,那么我们可以g h通过应用以下掩码来提取位0 0 0 0 0 0 1 1:

    a b c d e f g h
AND 0 0 0 0 0 0 1 1
  = 0 0 0 0 0 0 g h

请注意,has的值为3,在一般情况下只有2 ^ n - 1.

让我们用一些实数来尝试这个.假设我们想要计算42/4并得到商和余数:

42 = 0 0 1 0 1 0 1 0

为了得到商,我们向右移2位:

  42 / 4 (decimal)
= 0 0 1 0 1 0 1 0 >> 2
= 0 0 0 0 1 0 1 0
= 10 (decimal)

  42 MOD 4 (decimal)
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 1 0
= 2 (decimal)

所以42/4 = 10余数2.