1、前言

2、思路

有递归和迭代两种方法。
递归就是将原来的数切成一半，切的时候考虑奇数还是偶数。奇数往下切还需要乘 x，偶数不需要，但是为了统一也可以乘。然后考虑递归出口，分为3种情况：n == 0 则说明 n 为 1，直接返回1即可；n == 1 则说明 n 为2或3，直接返回 x；n 为-1 则说明 n 为 -2或-3，直接返回 1/x。
主体部分分为 half 与 rest。

迭代就是将指数变成2进制，比如5^3，则为5(0011)，只有2进制为1才有贡献，即 5^2 * 5^1，则可以迭代推出。

3、代码

递归：

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? myRec(x, N) : 1.0 / myRec(x, -N);
    }

    public double myRec(double x, long n){
        if(n == 0){
            return 1.0;
        }

        double half = myRec(x, n / 2);
        return n % 2 == 0 ? half * half : x * half * half;
    }
}

迭代：

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? myMulti(x, N) : 1.0 / myMulti(x, -N);
    }

    public double myMulti(double x, long n){
        double res = 1.0;
        while(n > 0){
            // 最低位是1，则说明有贡献
            if((n & 1) == 1){
                res *= x;
            }
            // 每一位不断累乘
            x *= x;
            // n 不断往右移动
            n = n >> 1;
        }

        return res;
    }
}