取模和与运算的优化

  1. 云栖社区>
  2. 博客列表>
  3. 正文

取模和与运算的优化

kryptosx 2016-05-27 23:01:36 浏览1534 评论0

摘要: 1 //来自coolshell的一个代码。 1 <span style="color: #000000;">int steps = 64 * 1024 * 1024; 2 // Arbitrary number of steps 3 int lengthMod = arr.

1 //来自coolshell的一个代码。
1 <span style="color: #000000;">int steps = 64 * 1024 * 1024;
2 // Arbitrary number of steps
3 int lengthMod = arr.Length - 1;
4 for (int i = 0; i < steps; i++)
5 {
6     arr[(i * 16) & lengthMod]++;   // (x & lengthMod) is equal to (x % arr.Length)
7 }
8 </span>

 

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

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

取模和与运算

 

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

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

转载请注明:旅途@KryptosX » 取模和与运算的优化

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

kryptosx
文章130篇 | 关注19
关注
阿里云数据库内置的智能专家,提供云数据库问题诊断、性能优化、SQL分析、资源分析、优化报告等... 查看详情
Node.js 性能平台(Node.js Performance Platform)是面向中... 查看详情
是阿里云安全专家基于阿里云多年安全最佳实践经验为云上用户提供的全方位安全技术和咨询服务,为云... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航