欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

为啥要用位运算代替取模呢

程序员文章站 2022-05-02 19:09:27
...

 

为什么很多开源软件中的源码中,使用位运算代替取模操作,比如:

a%b取模的形式都被替换成了a&(b-1) ,前提条件是:b为2的幂(乘方)

 

原因:

位运算实现取模只需5个CPU周期,而取模运算符实现至少需要26个CPU周期(注意,是最少!!!) 

 

原文:http://crazyjvm.iteye.com/blog/1725508

 

言归正传,大家都知道位运算的效率最高,这也是&取代%的原因,来看个程序:

C代码  为啥要用位运算代替取模呢
            
    
    博客分类: Algorithm 位运算 
  1. int main(int argc, char* argv[])  
  2. {  
  3.     int a = 0x111;  
  4.     int b = 0x222;  
  5.     int c = 0;  
  6.     int d = 0;  
  7.   
  8.     c = a & (b-1);  
  9.     d = a % b;  
  10.   
  11.     return 0;  
  12. }  

 

看反汇编的结果:

反汇编代码  为啥要用位运算代替取模呢
            
    
    博客分类: Algorithm 位运算 
  1. 13:       c = a & (b-1);  
  2. 00401044   mov         eax,dword ptr [ebp-8]  
  3. 00401047   sub         eax,1  
  4. 0040104A   mov         ecx,dword ptr [ebp-4]  
  5. 0040104D   and         ecx,eax  
  6. 0040104F   mov         dword ptr [ebp-0Ch],ecx  
  7. 14:       d = a % b;  
  8. 00401052   mov         eax,dword ptr [ebp-4]  
  9. 00401055   cdq  
  10. 00401056   idiv        eax,dword ptr [ebp-8]  
  11. 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周期(注意,是最少!!!) 效率显而易见。所以以后自己在写的时候,也可以使用前者的写法。

 

相关标签: 位运算