实现 pow(x,n) ，即求x的n次幂。使用暴力法超时，因而使用快速幂等法。

快速幂等法

要求一个数的n次幂，可以先求他的n/2次幂，一直分下去，简化问题，减少运算次数。
假设 A = x^(n/2)
如果 n%2 == 0，则 x^n = A * A;
如果 n%2 != 0，则 x^n = A * A * x;

• 可以采用循环法或者是递归法解决问题，时间复杂度均为 O(logN)

循环法

public double myPow(double x, int n) {
        //n是32位有符号整数，其数值范围是[−2^31, 2^31 − 1]。
        //如果直接将其 -n 转化为正数，有可能导致溢出
        //所以采用long类型储存n
        long N = n;

        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;

        for (long i = N; i > 0; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }

递归法

public double myPow(double x, int n) {
    long N = n;
    if (n < 0){
        N = -N;
        x = 1/x;
    }
    return myFastPow(x, N);
    }

public double myFastPow(double x, long n){
    if (n == 0)
        return 1;
        
    double half = myFastPow(x, n/2);

    if(n % 2 ==0)
        return half*half;
    else
        return half*half*x;
}

位运算法

此外还有一种位运算的方法，只说思路：把指数部分转换成2进制，然后展开成2的幂次的和。借用网上的图展示关系
以 x 的 10 次方举例。10 的 2 进制是 1010，然后用 2 进制转 10 进制的方法把它展成 2 的幂次的和。

• 时间复杂度为 O(N)
• 以上算法空间复杂度均是 O(1)