一种对2的n次方取余的优化方法
veekxt 发布于 2015-05-29 00:00:00

直接上结论:

m % 2^n == m & (2^n-1)

为什么呢?举个例子就很容易理解了,先考虑一个简单的事实:对2^n取余时,余数就是除数的最后几位,一个例子,1110110110110 % 100000 (二进制),写成右对齐:

0001110110110110
0000000000100000

除法的本质是减法,看上面的例子,很容易看出上面的数一直减下面的数,最终剩余的几位就10110,也就是余数, 实际上这个例子在其他进制中也很自然,比如12345 % 10^2==45,这不也是分离高位和低位的方法吗!那么现在问题就转化为了如何取最后几位,对于上面的例子, 一个方法就是让上面的数和111111进行位与,而它正好是100000(2^5)减一,于是上面的结论就显而易见了。

不过现代的编译器足够聪明, 大部分时候不需要人为地做这些自作聪明的优化。