按位与替换取余操作


由于我们知道位运算比较高效,在某些情况下,当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做&运算,正好取出的是其低位上的余数


Author: Moule Lin
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Moule Lin !
  TOC