博客

题目

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