Java：为什么 x % 2^n 等价于 x & (2^n - 1)？

Java：为什么 x % 2^n 等价于 x & (2^n - 1)？

• 案列
• 论证

案列

假设 x = 17，2^n取4，
那么17 % 4就等价于(4 * 4 + 1) = 1，17 & 4就等价于10001 & 11 = 00001 = 1

论证

x % 2^n = y 等价于 z * 2^n + y = x
先假设成立
那么 x & (2^n - 1) = y 等价于 z * 2^n + y & (2^n -1) = y
即 z * 2^n & (2^n - 1) = 0
由于 2^n & (2^n -1) = 0，而z是倍数
所以假设成立
所以 x % 2^n 等价于 x & (2^n - 1)