Question：

Implement pow(


x


,


n


).

Answer 1：

O（n）

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(n == 0) return 1;
        if(x == 0) return 0;
        
        bool flag = false;      // is negative
        if(n < 0) {
            flag = true;
            n = -n;
        }
        
        /*
        double ret = 1;
        for(int i = 0; i < n; ++i){        // error when n is max integer, such as n = 2147483647 overflow
            ret *= x;
        }
        */
        
        double tmp = x;
        double ret = 1;
        while(n > 0) {
            if(n & 1 == 1){     // or (n & 1) or (n % 2) or (n % 2 == 1)
                ret *= tmp;
            }
            tmp *= tmp;
            n >>= 1;
        }
        return flag ? 1.0/ret : ret;
    }
};

注意点：

题目非常简单，担忧许多细节需要考虑

1） x = 0 或 n = 0

2） n 为正或负数

3） n为正整数边界值（error 错误）

Answer 2：

O（log(n)）

class Solution {
public:
    
    double pow2(double x, int n){
        if(n == 0){
            return 1;
        }
        
        double mul = pow2(x, n/2);
        
        if(n & 1) {
            return x * mul * mul;
        } else {
            return mul * mul;
        }
    }
    
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(n < 0){
            return 1.0 / pow2(x, -n);
        } else {
            return pow2(x, n);
        }
    }
};

注意点：

1） 递归二分法

2） n为正/负数