50. Pow(x, n)

方法一：迭代

class Solution {
public:
    double myPow(double x, int n) {
        double res=1.0;
        for(int i=n;i!=0;i/=2){
            if(i%2) //奇数幂
                res*=x;
            x*=x;   
        }
        return n<0?1/res:res;
    }
};

方法二：递归

负数时没有用mypow(x,-n)，因为-2147483648转为正数超出int范围。

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n==1)
            return x;
        if(n==-1)
            return 1/x;
        double half=myPow(x,n/2);
        double res=myPow(x,n%2);
        return res*half*half;
    }
};