剑指 Offer 16. 数值的整数次方

原题链接：剑指 Offer 16. 数值的整数次方

 

solution:

        快速幂

①计算 x 的n次方是将 n个 x 连乘，效率比较低，会超时。
② 乘法具有结合律，考虑每次将一部分连乘批量计算好，作为最终答案的一部分。

class Solution {
public:
    typedef long long LL;
    double myPow(double x, int n) {
        bool is_minus = n < 0;
        double res = 1;
        for(LL k = abs(n);k;k >>= 1) {
            if(k & 1) res *= x;
            x *= x;
        }
        if(is_minus) return 1 / res;
        return res;
    }
};