数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

思路1：

最简单的方法就是把n个x相乘，考虑n=0和n<0的情况，n=0，结果为1，n<0,结果为1/x^-n。这个思路的时间复杂度为O(n),空间复杂度为O(1)。

代码：

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0) return 0;
        if(n == 0) return 1; 
        if(n < 0) {
            return 1 / myPow(x,-n);
        }
        double result = 1;
        for(int i = 1;i <=n;i++) {
            result *= x;
        }
        return result;
    }
};

思路2:

考虑公式：
aⁿ = a^n/2 * a^n/2 (n是偶数),aⁿ = a^n/2 * a^n/2 * a (n是奇数) ，a^n/2 同样可以应用这个公式。考虑n=0和n<0的情况,结果分别为1和1/a^-n 。时间复杂度为O(logN)，空间复杂度递归为O(logN)，迭代为O(1)。

代码：递归

class Solution {
public:
    double myPow(double x, long long n) {
        if(x == 0) return 0;
        if(n == 0) return 1; 
        if(n < 0) {
            return 1 / myPow(x,-n);
        }
        double half = myPow(x,n/2);
        if(n&1) {
            half = half*half*x;
        }
        else {
            half = half*half;
        }
        return half;
    }
};

代码：迭代。

公式还是上面的公式，查看规律。假设x = 2,n = 10,答案为a，则a和x = 4,n = 5的答案是相等的，显然，当n为偶数时，直接把x平方，n除以2。而a又和4倍的(x=16,n=2)相等。当n为奇数时，x继续平方，n也除以2，不过这样之后要乘以平方前的x才符合预期值。即n为奇数时，答案里要添加当时的x为结果的一个乘积因子。

class Solution {
public:
    double myPow(double x, long long n) {
        if(x == 0) return 0;
        if(n == 0) return 1; 
        if(n < 0) {
            return 1 / myPow(x,-n);
        }
        //初始化结果为1
        double result = 1.0;
        //初始化迭代因子为x
        double iteration = x;
        while(n>0) {
            //n如果为奇数，乘以此时的迭代因子。
            if(n&1) {
                result *= iteration;
            }
            iteration *= iteration;
            n /= 2;
        }
        return result;
    }
};