取模和与运算的优化

  • A+
所属分类:编程开发
//来自coolshell的一个代码。
int steps = 64 * 1024 * 1024;
// Arbitrary number of steps
int lengthMod = arr.Length - 1;
for (int i = 0; i < steps; i++)
{
    arr[(i * 16) & lengthMod]++;   // (x & lengthMod) is equal to (x % arr.Length)
}

注释中提到(x & lengthMod) is equal to (x % arr.Length)。
表示从没见到过这种优化啊,各种查资料才发现,其实这个有一个条件,即通常只有模去 2^n 才好直接用位运算做, x mod 2^n = x & (2^n-1)

至于原理,换算成二进制一切都清楚了。

取模和与运算的优化

IP地址掩码

取模和与运算的优化

左移动和右移动

我们可以发现,因为除数是2^n,那么它二进制是一个1000..0(n个0)的形式。x在从n位(从右往左数)开始必然是2^n的倍数。取模的话,就是从右往左数n-1位的值。所以,让x^n-1使得那块全变为1,然后进行与运算,就得到模值了。

相对于通常的取模,位运算会更快。这是个不错的优化。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: