昨天的分析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做&运算,得出来的低位就是我们期望的余数。