Sword finger offer 16 Integer power of numeric value

Original link ： The finger of the sword Offer 16. Integer power of value

 

solution:

        Fast power

① Calculation x  Of n To the power of n individual x  multiply continuously , Low efficiency , Will timeout .
② Multiplication has the law of association , It is considered to calculate a part of the serial multiplication batch each time , As part of the final answer .

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;
    }
};