【筆記】C++快速冪

快速冪:用 O(log n) 的時間快速計算 a 的 b 次方是多少。
原理:如果 b 的二進位中第 i 項(最右項為第 0 項)為「1」,答案會包含乘以 a^(2^i)。

int fastpow(int a, int b){
    int ans = 1;
    for(int i=0; (1 << i) <= b; i++){
        if(b & (1 << i)) ans *= a;
        a *= a;
    }
    return ans;
}

1 << 0 = 1
1 << 1 = 10
1 << 2 = 100

(b & (1 << i)) 可以用來判斷 b 的二進位制從右至左是否為「1」。

參考文章:henrybear327.gitbooks.io

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。