leetcode 50. Pow(x, n)

50. Pow(x, n)

要特别注意 n 的范围 ，如果 n = -2^31，使用int 是不可以直接 n = -n; 的

一、使用long

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0)  return 0;
        if(n == 0)  return 1;
        if(n == 1)  return x;

        long nTemp = n;
        if(nTemp < 0){
            x = 1.0/x;
            nTemp = -nTemp;
        }

        double res = 1.0;
        long count = 0;
        vector<double> mult;
        mult.push_back(x);
        //比如n = 35，那么两两平方的次数为log(35)向下取整
        //x^1  x^2  x^4  x^8  x^16  x^32   最多平方5次
        int log2 = (int)(log(nTemp)/log(2));
        for(int i = 0;i < log2;i++){
            double t = mult.back();
            mult.push_back(t*t);
        }
       
        int size = mult.size();
        for(int i = size-1;i >= 0;i--){
            if(count + pow(2,i) <= nTemp){
                res *= mult[i];
                count += pow(2,i);//count代表目前res=x^count
            }
        }
        return res;
    }
};        

二、不使用long

不使用long就要对边界条件单防了

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0)  return 0;
        if(n == 0)  return 1;
        if(n == 1)  return x;
        if(x == 1)  return 1;
        if(x == -1){
            if(n == INT_MIN)  return 1;
            if(n < 0)  n = -n;
            if(n%2==0)  return 1;
            else  return -1;
        }
        if(n == INT_MIN){
            if(abs(x)>1)  return 0;
            return (1.0/x)*myPow(1.0,INT_MAX);
        }

        if(n < 0){
            x = 1.0/x;
            n = -n;
        }

        double res = 1.0;
        int count = 0;
        vector<double> mult;
        mult.push_back(x);

        int log2 = (int)(log(n)/log(2));
        for(int i = 0;i < log2;i++){
            double t = mult.back();
            mult.push_back(t*t);
        }
       
        int size = mult.size();
        for(int i = size-1;i >= 0;i--){
            if(count + pow(2,i) <= n){
                res *= mult[i];
                count += pow(2,i);
            }
        }
        return res;

    }
};

222