当前位置：首页 > news >正文

50. Pow(x, n)快速幂算法

news 2025/6/26 11:58:06

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。此函数应将 x 作为浮点数（意味着它可以是十进制数）和 n 作为整数（可以是正数、负数或零）一起使用。

快速幂（Exponentiation by Squaring） 的时间复杂度是 O(log n)，而不是 O(n)。因此比普通连续相乘的暴力解法快很多，尤其在指数很大时更为明显。

快速幂利用了指数的 二进制分解。关键在于每次指数都除以 2（右移）。

代码：

class Solution {public double myPow(double x, int n) {// If power n is non-negative, calculate power using helper method// 如果指数 n 是非负数，直接调用辅助方法计算if (n >= 0) {return quickPow(x, n);} else {// If power n is negative, calculate the inverse of the power// 如果指数 n 是负数，先转成 long 类型防止溢出，然后计算倒数return 1 / quickPow(x, -(long) n);}}private double quickPow(double base, long exponent) {double result = 1; // Initialize result to neutral element for multiplication// 初始化结果为 1（乘法的单位元）// Loop through all bits of the exponent// 遍历指数的每一位（二进制）while (exponent > 0) {// If the current bit is set, multiply the result by the base// 如果当前位是 1（即指数是奇数），说明该位有效，就把当前 base 乘进结果中if ((exponent & 1) == 1) {result *= base;}// Square the base for the next bit in the exponent// 每处理一位，把 base 平方，指数除以 2，平方乘法base *= base;// Shift exponent to the right to process the next bit// 指数右移一位，继续处理下一个最低位exponent >>= 1;}// Return the final result of base raised to the exponent// 返回最终结果return result;}
}

平方乘法的数学原理

我们知道：

x² = x * x
x⁴ = (x²)²
x⁸ = (x⁴)²

也就是说：

x^2k = (x^k)^2

这说明：

如果我们每次把底数平方，就相当于一次性“处理了两个幂”。

⛳ 示例过程：a = 2, n = 13

n	n 的二进制	当前位	result 操作	base 操作	新 result	新 base
13	1101	1	result *= base	base = base²	2	4
6	0110	0	-	base = base²	2	16
3	0011	1	result *= base	base = base²	32	256
1	0001	1	result *= base	base = base²	8192	65536
0	0000	-	结束

如果指数 n 是负数，先转成 long 类型防止溢出

Java 中 int 类型的取值范围是：
👉 [-2³¹, 2³¹ - 1]
👉 即 [-2147483648, 2147483647]

int n = Integer.MIN_VALUE; // n = -2147483648
int positive = -n; // 正常来说你想让它变成 2147483648

System.out.println(positive); // 实际输出：-2147483648（依然是负数！）
为什么？因为 2147483648 超出了 int 最大值！

✅ 解决方法：先转成 long
return 1 / quickPow(x, -(long) n);
这样 -(long) n 的计算就不会发生溢出了：

long 是 64 位的，能表示的范围非常大：

-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807

比 int 的表示范围大得多，所以：

long n = Integer.MIN_VALUE; // n = -2147483648 long positive = -n; // 不会溢出 System.out.println(positive); // 输出：2147483648 ✅

🔍 为什么这在快速幂中很重要？
因为我们要把 n 转为正数，才能做快速幂：

如果你不转为 long，那么：
quickPow(x, -n); // 这里 -n 就可能等于 Integer.MIN_VALUE
就会导致逻辑错误甚至死循环（因为指数没变正）。

📘 看一下几个重要值及其补码：

十进制值	二进制补码表示	注释说明
`-2147483648`	`10000000 00000000 00000000 00000000`	最小的 int，符号位为 1，其他全 0
`-2147483647`	`10000000 00000000 00000000 00000001`	第二小，最低位是 1
`-1`	`11111111 11111111 11111111 11111111`	补码中所有位都是 1
`0`	`00000000 00000000 00000000 00000000`	全 0
`1`	`00000000 00000000 00000000 00000001`	正数，从 1 开始递增
`2147483647`	`01111111 11111111 11111111 11111111`	int 能表示的最大值