ruby - 按位与作为模数替代

Question

我想知道为什么以下表达式会产生相同的结果:

# method 1
def produce(n)
  n % 16
end

#method 2
def produce(n)
  n & 15
end

我了解到方法 1 使用模运算，方法 2 使用“按位与”。但我有点迷惑为什么用 15 调用 & 与调用模 16 相同。

我有一种预感，它只适用于 modulo x，其中 x 是 2^n。有什么想法吗？

Answer 1

您正确地认为这与模 2^n 有关。让我们看一下它是如何分解为二进制的。

第一个以 16 为模的方法在二进制中看起来像这样:

10000

按位与 15 比较:

01111

从本质上讲，您对模数或余数所做的就是得到除以 16 后剩下的部分。因为它是 2 的幂，所以您实际上是在删除 16 以上的所有位，因为它们平均分配并留下任何位低于 16。

使用按位，你也在做同样的事情。您将每一位都保持在 16 以下并给自己相同的结果。

这适用于任何数字 % 2^n 和 & (2^n - 1)