代码优化之优化除法

《代码优化之优化除法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、说明：文章中的很多数据可能在新的CPU或不同的CPU或不同的系统环境下有不同的结果，可能不能面面俱到)x86系列的CPU对于位运算、加、减等基本指令都能在1个CPU周期内完成(现在的CPU还能乱序执行，从而使指令的平均CPU周期更小)；现在的CPU,做乘法也是很快的(需要几个CPU周期，每个周期可能启动一个新的乘指令)，但作为基本指令的除法却超出很多人的预料，它是一条很慢的操作，整数和浮点的除法都慢；我测试的英特尔P5赛扬CPU浮点数的除法差不多是37个CPU周期，整数的除法是80个CPU周期，AMD2200+浮点数的除法差不多是21个CPU周期，整数的除法是4

2、0个CPU周期。(改变FPU运算精度对于除法无效)(SSE指令集的低路单精度数除法指令DIVPS18个CPU周期,四路单精度数除法指令DIVSS36个CPU周期)(x86求余运算和除法运算是用同一条CPU指令实现的；据说，很多CPU的整数除法都是用数学协处理器的浮点除法器完成的；有一个推论就是，浮点除法和整数除法不能并行执行.(ps:intel的p4imul指令可能有14周期(或15-18)的延迟才能得到结果)本文将给出一些除法的优化方法或替代算法(警告:某些替代算法并不能保证完全等价!)1.尽量少用除法比如：if(x/y>z)...改成：if(((y>0)

3、&&(x>y*z))

4、

5、((y<0)&&(x=count)index=index%count;//assert(index=count)index=index-count;2.用减法代替除法如果知道被除数是除数的很小的倍数，那么可以用减法来代替除法比如：uint32x=200;uint32y=70;uint32z=x/y;改成：uintz=0;while(x>=y){x-=y;++z;}一个用减法和移位完成的除法(如果你没有除法指令

6、可用:)uint32div(uint64u,uint32z)//returnu/z{uint32x=(uint32)(u>>32);uint32y=(uint32)u;//y保存商x保存余数for(inti=0;i<32;++i){uint32t=((int32)x)>>31;x=(x<<1)

7、(y>>31);y=y<<1;if((x

8、t)>=z){x-=z;++y;}}returny;}(该函数经过了测试；z==0需要自己处理；对于有符号除法，可以用取绝对值的方法(当然也不是轻松就能写出完全等价的有符号除法的:)；如果不需s的64bit长度，仅需要32bit,

9、那么可以化简这个函数，但改进不多)3.用移位代替除法(很多编译器能自动做好这个优化)要求除数是2的次方的常量；(同理：对于某些应用，可以优先选取这样的数来做除数比如：uint32x=213432575;)uint32y=x/8;改成：y=x>>3;对于有符号的整数；比如：int32x=213432575;int32y=x/8;改成：if(x>=0)y=x>>3;elsey=(x+(1<<3-1))>>3;4.合并除法(替代方法不等价，很多编译器都不会帮你做这种优化)适用于不能用其它方法避免除法的时候；比如：doublex=a/b/c;改成：doublex=a/

10、(b*c);比如：doublex=a/b+c/b;改成：doublex=(a+c)/b;比如：doublex=a/b;doubley=c/d;doublez=e/f;改成：doubletmp=1.0/(b*d*f);doublex=a*tmp*d*f;doubley=c*tmp*b*f;doublez=e*tmp*b*d;5.把除法占用的时间充分利用起来CPU在做除法的时候，可以不用等待该结果(也就是后面插入的指令不使用该除法结果)，而插入多条简单整数指令(不包含整数除法，而且结果不能是一个全局或外部变量等)，把除法占用的时间节约出来；(当除法不可避免的时候，这

11、个方法很有用)6.用查表的方法代替除法（适用于除数和被除数的可能的取值范围较小的情况，否则空间消耗太大）比如uint8x;uint8y;uint8z=x/y;改成uint8z=table[x][y];//其中table是预先计算好的表，table[i][j]=i/j;//对于除零的情况需要根据你的应用来处理或者：uint8z=table[x<<8+y];//其中table[i]=(i>>8)/(i&(1<<8-1));比如uint8x;uint8z=x/17;改成uint8z=table[x];//其中table[i]=i/17;7.用乘法代替除法(替代

12、方法不等价，很多编译器都