[转载]使用位运算代替乘除法
原文地址:使用位运算代替乘除法作者: cc3000c 已知 : nsigned int temp=1000； nsigned int res lt=0； 要求出res lt = val e * 10% 最直接的方法是 : res lt = (temp * 10)  100； 使用位运算的方法是 : res lt = (temp  4) + (temp  5) + (temp  8) + (temp  9)； 在mplab(picc-v9.70-lite mode)下测试得到的结果显示使用位运算需要的时间仅为乘除法运算的4分之1。 先看测试代码、比较一下两种表示方法,再来看如何使用位运算的表示方法。 测试代码 : #incl de __config(0x3f3a)； nsigned int temp=1000； nsigned int res lt1=1； nsigned int res lt2=1； int main(void) { res lt1 = (temp4) + (temp5) + (temp8) + (temp9)； 位运算 asm("nop")； asm("nop")； res lt2 = ( temp *10 )100； 乘除法 asm("nop")； asm("nop")； while(1) ； } 在mplab中没有更改晶振、的按默认的20mhz调试的。 使用 asm("nop")； 是为了调试的方便。 结果为 :res lt1 = 97、res lt2 = 100； 由位运算求出的10%误差是3%、而乘除法的结果没有误差。 在很多情况下都不需要绝对精确的结果、所以上面的差值3是完全可以接受的。 下面来看看使用位运算和乘除法需要的执行时间 : instr ction cycles time( secs) 位运算 222 444 乘除法 851 1702 使用位运算需要的时间大概是乘除法运算的4分之1。 在反汇编代码中可以看到、乘除法运算过程中调用了乘法和除法的函数(是mplab自带的) : 乘法 : 即0x709处定义的乘法 : 除法 : 即0x734处定义的除法: 执行乘发和除法需要的时间为 : instr ction cycles time( secs) __wm l 305 610 __lwdiv 505 1010 执行乘法或除法需要的时间都远远比整个位运算多得多。 使用这种位运算有几个限制条件 : 1、需要知道系数、比如上面的10%、当然、这个系数是120%、或是8倍都是一样的。 2、结果允许一定的误差、比如上面的97、差值是3。这个误差可大可小、接下来会讲到。 现在来看看上面使用的位运算 : 求temp的10%的表达式 res lt = (temp  4) + (temp  5) + (temp  8) + (temp  9)； 是怎么来的呢。 x64、用移位表示就是x6、知道这种表示法、自然就会明白了。 10%用二进制表示出来就是 : 1(2^4) + 1(2^5) + 1(2^8) + 1(2^9) = 0.0、即9.96%、约等于10%。 所以结果就是 : = temp * ( 1(2^4) + 1(2^5) + 1(2^8) + 1(2^9) ) = temp  (2^4) + temp  (2^5) + temp  (2^8) + temp  (2^9) = (temp  4) + (temp  5) + (temp  8) + (temp  9) 这里注意要加括号  、因为移位运算的优先级比加减法低 10%用到减法来表示的情况 : (1(2^3) - 1(2^5) + 1(2^7) -1(2^9)) = 0.0 计算时使用天下计算器之类的计算软件会很快的得到结果 : 误差 : 方法很简单、但是要注意误差的存在。 我们的表达式里面有4个部分1(2^4) + 1(2^5) + 1(2^8) + 1(2^9)、 如果只要三项1(2^4) + 1(2^5) + 1(2^8)、结果就是0.0=9.76% 误差增大了、要得到越小的误差、需要的项数就越多。 使用5项时误差更小1(2^4) + 1(2^5) + 1(2^8) + 1(2^9) + 1(2^11)= 0.=10.00%。 但是使用的项数运算量越大,而且移位的位数越大、运算量也越大。 temp9需要移位次、temp11需要移位10次。 所以只要误差可接受即可、不必耗费更多的代价来得到更高的精度。 空间 : 当然、最好的方法还是将结果做成数组、使用查表取值。 没有运算、不用考虑耗时、也不用担心运算出错。 比如将255分成100份 : const nsigned char table[100]={ 2, 5, 7, 10, 12, 15, 17, 20, 22, 25, 1%~10% ... . ... 90%~100% }； 耗费flash中的100个byte并不算多、很多时候flash都用不完的。