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

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

分析：

方法1：快速幂+迭代

先简单介绍一下快速幂，比如说 x = 2， n 为 10，n 转化为二进制就是1010，那么输出的就为 2^(1010) = 2^(1*2^3 + 0*2^2 + 1*2^1 +  0*2^0) = 2^(2^3) * 2^2，本来 O(n) 的时间复杂度就降到了 O(log n)，那么我们可以将每一位的运算看做 x *= x，那么有 1 的情况就是例外，单独乘起来，最后将这个单独乘的变量和结果相乘就是答案。判断是否有 1 可以直接和 1 做与运算，然后将 n 右移，直到 n = 1。需要注意的是，n 为负数时取反，然后将 x 令为 1/x 即可，但是取反时可能越界，索引将 n 的类型转化为长整型（long）。

时间复杂度：O(log n)
空间复杂度：O(1)

class Solution {
    public double myPow(double x, int n) {
        //任何数的零次方都是 1
        if(n == 0){
            return 1.0;
        }
        //防止 n 取反时越界
        long n2 = n;
        // n 小于零取反，x 取倒数
        if(n < 0){
            x = 1 / x;
            n2 = -n2;
        }
        //定义结果
        double sum = 1.0;
        while(n2 != 1){
            //取余为 1 时
            if((n2 & 1) == 1){
                sum *= x;
            }
            x *= x;
            //右移一位
            n2 >>= 1;
        }
        return sum * x;
    }
}

方法2：快速幂+递归

时间复杂度：O(log n)
空间复杂度：O(1)

class Solution {
    public double myPow(double x, int n) {
        //任何数的零次方都是 1
        if(n == 0){
            return 1.0;
        }
        //n 为负数情况
        if(n == -1){
            return 1 / x;
        }
        //n 为正数
        if(n == 1){
            return x;
        }
        return myPow(x * x, n >> 1) * myPow(x, n & 1);
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof