使用位运算替代模运算

昨天的分析HashMap原理的文章里面提到，使用位运算替代取模运算效率高，但位运算只能在特定场景下才能替代%运算。

正常情况下：

但如果b的值为2的n次方的时候（n为自然数），这时候就可以用位运算来替代模运算， 转化如下：

2的n次方的二进制如下：

从上面能看到左移一位是放大2倍，右移一位是缩小2倍

分别减一后的二进制

举例

我们算下11%8的模，

11的二进制是：1011

代入上面的公式：

7的二进制： 0111

二者做&(与)运算 ，回忆下运算规则：

结果：

1011 & 0111 = 0011

转化成10进制后=3

所以11%8=3

这种方法只是适合于求一个数除以二的N次冥才正确，求模的过程，就是2^n-1的中1的个数就是n的值，再与a做&运算，得出来的低位就是我们期望的余数。