快速幂算法——求解大指数幂
定义+适用范围
快速幂算法（Fast Exponentiation）是一种高效的计算幂的方法，特别适用于计算形如 a^b的表达式，其中 a 是底数，b 是指数，且 b 可能非常大。
核心思想
快速幂算法的核心思想是将指数 b 表示为二进制形式，并利用二进制数的性质来减少乘法操作的次数。
基本思想
-
将指数 b 转换为二进制表示：例如，如果 b=13，则其二进制表示为 1101(2)。
-
从右到左遍历二进制数的每一位：对于 b=13(10)=1101(2)，我们从右到左遍历每一位（即 1,0,1,1）。
-
根据当前位是 0 还是 1 来决定是否将当前的底数的幂乘到结果中：
- 如果当前位是 1，则将当前的底数的幂乘到结果中。
- 如果当前位是 0，则不乘。
-
底数的幂每次循环都平方：在每次循环中，我们都将底数的当前幂平方，以便在下一次循环中使用。
-
指数每次循环都右移一位：这相当于将指数除以 2（在二进制表示中）。
示例
假设我们要计算 2^13。
- 13(10)=1101(2)
- 初始化
result = 1，base = 2（result为结果，base为底数） - 遍历 1101(2) 的每一位：
- 最低位是 1，
result *= base^1（即result *= 2），然后base = base^2（即base = 4），指数右移一位（现在考虑 110(2)） - 下一位是 0，不乘，
base = base^2（即base = 16），指数右移一位（现在考虑 11(2)） - 下一位是 1，
result *= base^1（即result *= 16），然后base = base^2（即base = 256），指数右移一位（现在考虑 1(2)） - 最高位是 1，
result *= base^1（即result *= 256）
- 最低位是 1，
最终，result = 2 * 4 * 16 * 256 = 8192，即 2^13=8192。
代码实现
public double myPow(double x, int n) { long N = n; // 使用 long 防止溢出 if (N == 0) return 1.0; boolean isNegative = N < 0; N = Math.abs(N); double result = 1.0; double base = x; while (N > 0) { if ((N & 1) == 1) { // 如果 N 的当前最低位是 1 result *= base; } base *= base; // base 平方 N >>= 1; // N 右移一位（相当于除以 2） } if (isNegative) { result = 1.0 / result; } return result;
}