当前位置： 移动技术网 > IT编程>开发语言>Java > Pow(x, n)（快速幂+迭代实现）

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

2020年07月13日  | 移动技术网IT编程  | 我要评论

题目

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

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

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

注意点

1、n使用long类型存储，避免-N时出现溢出；
2、n = 10 = (1010)2 = 0 + 21 + 0 + 2 3;
3、 x10 = x^ (21 + 2 3) = x 2 * x8;
4、由上面可知，当指数对应的二进制位为0时，不需要计算入结果；当指数对应的二进制位为1时，需要计算入结果；所以从x开始不断地进行平方，得x、x2、x4、x8，如果 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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网