Pow(x, n)（快速幂+迭代实现）

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

说明:
1、-100.0 < x < 100.0；
2、n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

示例 :
输入: 2.00000, 10
输出: 1024.00000

注意点

1、n使用long类型存储，避免-N时出现溢出；
2、n = 10 = (1010)₂ = 0 + 2¹ + 0 + 2 ³;
3、 x¹⁰ = x^ (2¹ + 2 ³) = x ² * x⁸;
4、由上面可知，当指数对应的二进制位为0时，不需要计算入结果；当指数对应的二进制位为1时，需要计算入结果；所以从x开始不断地进行平方，得x、x²、x⁴、x⁸，如果 n 的对应的二进制位为 1，那么我们就将对应的值计入结果。

实现

class Solution {
    public double myPow(double x, int n) {
    	//使用long，避免-N时出现溢出
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

	//快速幂
    public double quickMul(double x, long N){
        //记录结果
        double ans = 1;
        //记录中间量
        double X = x;

        while(N > 0){
        	//如果n的二进制位为1，将该值乘于结果
            if(N % 2 == 1){
                ans *= X;
            }
            
			//中间量平方
            X *= X;
            N /= 2;
        }
        return ans;
    }
}

本文地址：https://blog.csdn.net/weixin_43857345/article/details/107252000