【leetcode】Pow(x, n)

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は正/負