由于我们知道位运算比较高效,在某些情况下,当b为2的n次方时,有如下替换公式:
a % b = a & (b-1)
notes:
- b必须为2的整数倍
因为可以保证b始终只有最高位为1,其他二进制位全部为0,减去1,之后,可以把高位1消除,其他位都为1。
减一之后,最高位为0,之后都为1(b,b剩下的数就是需要的余数的最高值),就相当于计算低位与原数的与
例如:14%8,取余数,相当于取出低位,而余数最大为7,14二进制为1110,8的二进制1000,8-1 = 7的二进制为0111,由于现在低位全为1,让其跟14做&运算,正好取出的是其低位上的余数