java - 当n为2^k时，如何证明m%n等价于m&(n-1)？

Question

请注意，“%”是余数运算符，“&”是按位与运算符，k 是大于 0 的整数。

例子：

33%16=1 equivalent to 33&(16-1)=1

我在 JDK1.8 ThreadLocalMap 中找到了这个等价物。我知道这是正确的，但不知道如何证明它是正确的。如果您能提供一些帮助，我将不胜感激。

标签： javadictionaryhashhashmapthread-local

Answer 1

m % n是 m 除以 n 的余数，因此是介于 0 和 n-1 之间或介于 0 和 2^k - 1 之间的数字。

二进制中的 2^k 是 1 后跟 k 个零。2^k -1 是 k 个连续的。

m & n是 m & (2^k - 1) 是一个数字，其中，在二进制中，1 位必须出现在最右边的 k 位中。因此它在 0 到 2^k - 1 的范围内。

QED。