为什么很多开源软件中的源码中,使用位运算代替取模操作,比如:
a%b取模的形式都被替换成了a&(b-1) ,前提条件是:b为2的幂(乘方)。
原因:
位运算实现取模只需5个CPU周期,而取模运算符实现至少需要26个CPU周期(注意,是最少!!!)
原文:http://crazyjvm.iteye.com/blog/1725508
言归正传,大家都知道位运算的效率最高,这也是&取代%的原因,来看个程序:
- int main(int argc, char* argv[])
- {
- int a = 0x111;
- int b = 0x222;
- int c = 0;
- int d = 0;
- c = a & (b-1);
- d = a % b;
- return 0;
- }
看反汇编的结果:
- 13: c = a & (b-1);
- 00401044 mov eax,dword ptr [ebp-8]
- 00401047 sub eax,1
- 0040104A mov ecx,dword ptr [ebp-4]
- 0040104D and ecx,eax
- 0040104F mov dword ptr [ebp-0Ch],ecx
- 14: d = a % b;
- 00401052 mov eax,dword ptr [ebp-4]
- 00401055 cdq
- 00401056 idiv eax,dword ptr [ebp-8]
- 00401059 mov dword ptr [ebp-10h],edx
可以看到,&操作用了:3mov+1and+1sub %操作用了:2mov+1cdp+1idiv
我们可以查阅Coding_ASM_-_Intel_Instruction_Set_Codes_and_Cycles资料,发现前者只需5个CPU周期,而后者至少需要26个CPU周期(注意,是最少!!!) 效率显而易见。所以以后自己在写的时候,也可以使用前者的写法。
相关推荐
斐波那契数列的几种时间复杂度优化 以下代码因不同算法而时间复杂度不同个人归类为不同版本,总结如下。 1.尽量不要用递归,纵使好看,但...4.用位运算来代替乘法、除法以及取模。 5.有数学公式用数学公式@.@....
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
&= 运算符 对变量和表达式执行按位“与”运算,结果赋给变量。 && 运算符 对两个表达式执行逻辑连接运算。 * 运算符 将两个表达式的值相乘。 *= 运算符 将变量与表达式的值相乘,结果赋给变量。 + 运算符 将两个...
Stein 的算法用算术移位、比较和减法代替除法。Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。欧几里德算法是计算两个数...
欢迎使用 JScript 语言参考 这些方便实用的信息将帮助您了解 JScript 的各个部分。 在“字母顺序的关键字列表”中,可以找到按字母顺序列出的所有 JScript 语言的主题。如果只需要查看某个主题(例如对象),则有对...
&= 运算符 对变量和表达式执行按位“与”运算,结果赋给变量。 && 运算符 对两个表达式执行逻辑连接运算。 * 运算符 将两个表达式的值相乘。 *= 运算符 将变量与表达式的值相乘,结果赋给变量。 + 运算符 将两个...
5.9 什么时候应该用宏代替函数? 5.10 使用宏更好,还是使用函数更好? 5.11 在程序中加入注释的最好方法是什么? 5.12 #include和#include“file”有什么不同? 5.13 你能指定在编译时包含哪一个头文件吗? ...
然后再申明一个OleDbDataReader,来读取数据,用的是ExecuteReader(),objDataReader.Read()就开始读取了,在输出的时候我们要注意Text属性接受的只能是字符串,所以我们要把读出的数据都转化为字符串才行。...
5.9. 什么时候应该用宏代替函数? 83 5.10. 使用宏更好,还是使用函数更好? 83 5.11. 在程序中加入注释的最好方法是什么? 83 5.12. #include 和#include“file”有什么不同? 84 5.13. 你能指定在编译时包含哪一个...
4 软 件 最 终 产 品 :用 Java 语 言 开 发 的 软 件 可 以 具 有 可视化 、 可 听 化 、 可 操作 化 的 效 果 ,这 要 比 电 视 、 电 影 的 效果 更 为 理 想 ,因 为 它 可 以做 到 "即 时 、 交 互、 动 画 与 ...