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

Question

我发现了一些示例源代码，其中作者似乎使用按位 &运算符而不是 %运算符(operator)。然而，当我尝试 x & 4它不会产生与 x % 5 相同的值.

Answer 1

这仅适用于 2 的幂。

一般来说:

x MOD 2^n

相当于:

x AND (2^n - 1)

另请注意，这可能仅适用于 x >= 0 ，取决于您对 MOD 的定义为 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。