欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-16 17:47:43
题目实现 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、由上面可知,当指...

题目

实现 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