[心得] 整數pow O( 1 + log2(N) ) complexity …
下這個標題主要是看到太多的資結考試用書都用很長的遞迴程式碼完成這件事情
:(
以下的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)
推
02/18 10:17, , 1F
02/18 10:17, 1F
推
02/18 10:27, , 2F
02/18 10:27, 2F
推
02/18 12:43, , 3F
02/18 12:43, 3F
→
02/18 21:06, , 4F
02/18 21:06, 4F
→
02/18 22:29, , 5F
02/18 22:29, 5F