作者sunneo (艾斯寇德)
看板C_and_CPP
标题[心得] 整数pow O( 1 + log2(N) ) complexity 非递回解
时间Wed Feb 18 10:15:19 2009
下这个标题主要是看到太多的资结考试用书都用很长的递回程式码完成这件事情
:(
以下的pow 乘法次数总计
N ^ 32 共执行6次乘法 == 1 + floor( log2(POW) )
N ^ 21474863647 共执行62次
exp的各个bit栏位相当於原数乘上几次，这些bit恰好以2的倍数增长=> 1,2,4,8,16,32
原数字与自己相乘恰好可以得到次方乘2的效果
只要再该bit有set的时候将目前的结果乘上即可
所以得到下面的程式码
int fastpow(
int a,
int b){
int ret = 1;
for( ; b>0; b>>=1, a*=a){
if(b&1){
ret *= a;
}
}
return ret;
}
喜欢简短的可以考虑下面的形式
int fastpow(
int a,
int b){
int ret = 1;
for( ; b>0; b>>=1, a *= a){
ret *= (b&1)?a:1;
}
return ret;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.228.180
※ 编辑: sunneo 来自: 61.227.228.180 (02/18 10:16)
1F：推 ledia:这是很常用的加速, 不过次方大时, 你还得需要大数运算 02/18 10:17
2F：推 wa120:推XD 02/18 10:27
3F：推 VictorTom:推:) 02/18 12:43
4F：→ bleed1979:程式之美-微软技术面试心得 p.167 02/18 21:06
5F：→ sunneo:@@感谢楼上推荐这本书 我还没看过呢 02/18 22:29