实现 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
-231 <= n <= 231-1
-104 <= xn <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

这里

求解x的n次幂的时候，我们可以用快速幂算法求解，
例如x⁷⁷，我们可以可以抽象为：x⁷⁷ = x⁶⁴ ✖ x⁸ ✖ x⁴ ✖ x¹，
77的二进制表示为：

         1       0     0     1     1     0     1
        x^64   x^32   x^16  x^8   x^4   x^2   x^1

所以我们仅需要将n次幂数二进制的非零位对应的权重相乘即可。提供两种算法，一种是递归求解，一种是迭代，迭代的好处就是只应用常数的空间，空间效率是O(1)。

public class Solution {

    /**
     * @description: 快速幂加递归解法
     * @author: Abean
     * @date: 2022/7/14 12:12
     * @param: [x, n]
     * @return: double
     **/
    public double myPow(double x, int n) {
        long y = n;
        return y < 0 ? getPow(1 / x, -y) : getPow(x, y);
    }

    public double getPow(double x, long n) {
        if (n == 0) return 1.0d;
        double res = 1;
        while (n > 0) {
            if ((n & 1) == 1) res *= x;
            x *= x;
            n >>= 1;
        }

        return res;
    }

    /**
     * @description: 快速幂加迭代解法
     * @author: Abean
     * @date: 2022/7/14 12:13
     * @param: [x, n]
     * @return: double
     **/
    public double pow(double x, int n) {
        if (x == 0) return 0;
        if (n == 0) return 1;
        // 防止溢出
        long y = n;
        // 若y<0，即求1/x的y次幂
        if (y < 0) {
            x = 1 / x;
            y = -y;
        }

        double res = 1, weight = x;
        while (y > 0) {
            // 若当前二进制位为1，结果乘以权值
            if ((y & 1) == 1) res *= weight;
            weight *= weight;
            // 移位
            y >>= 1;
        }

        return res;
    }
}

结果如下：

递归 迭代