推 ledia:這是很常用的加速, 不過次方大時, 你還得需要大數運算 02/18 10:17
推 wa120:推XD 02/18 10:27
推 VictorTom:推:) 02/18 12:43
→ bleed1979:程式之美-微軟技術面試心得 p.167 02/18 21:06
→ sunneo:@@感謝樓上推薦這本書 我還沒看過呢 02/18 22:29
下這個標題主要是看到太多的資結考試用書都用很長的遞迴程式碼完成這件事情
:(
以下的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)