本文详解 Java 实现快速幂取模时因整数溢出导致结果错误的根本原因，并提供基于 long 的安全实现及关键注意事项，确保大指数幂运算（如 2^10⁹ mod 10⁹+7）结果准确。
本文详解 java 实现快速幂取模时因整数溢出导致结果错误的根本原因，并提供基于 `long` 的安全实现及关键注意事项，确保大指数幂运算（如 2^10⁹ mod 10⁹+7）结果准确。
在 Java 中实现模幂运算（如计算 $2^{10^9} \bmod (10^9+7)$）时，看似正确的快速幂代码仍可能输出错误结果（例如预期 336781474 却得到 140625001），其根本原因并非算法逻辑错误，而是中间计算过程中的整数溢出——尤其发生在 base * base 或 result * base 这类乘法操作中。
回顾原代码问题所在：
int mod = (int) (1e9) + 7; // ✅ 正确：1000000007
int modPow(long base, long exponent) {
if (exponent == 0) return 1;
long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % mod; // ⚠️ 危险！result 和 base 均为 long，
// 但乘积可能远超 long 范围（如 10^9+7 ≈ 1e9，
// 则 (1e9)^2 = 1e18 —— 接近 long 上限 9.2e18，
// 但多轮平方后极易溢出）
}
base = (base * base) % mod; // ⚠️ 同样存在溢出风险
exponent /= 2;
}
return (int) result;
}
⚠️ 关键误区：
虽然 base 和 result 声明为 long，但 mod 是 int（值为 1000000007）。当执行 (result * base) % mod 时，Java 先计算 result * base（两个 long 相乘），结果仍是 long；但若该乘积超过 Long.MAX_VALUE（≈9.2×10¹⁸），就会静默溢出，导致后续取模结果完全错误。例如：
-
base ≈ 1e9→base * base ≈ 1e18（尚可） - 但经过若干次迭代后，
base可能接近1e9+7，而result也可能达同量级，此时result * base可突破9.2e18，触发long溢出。
✅ 正确做法：所有乘法前强制转为 long 并确保模数也为 long，避免隐式类型窄化；更稳妥的是统一使用 long 类型参与全部算术运算，并在每次乘法后立即取模：
class Solution {
private static final long MOD = 1_000_000_007L; // ✅ 显式 long，避免 int 提升隐患
long modPow(long base, long exponent) {
if (exponent == 0) return 1L;
long result = 1L;
base %= MOD; // 预处理：确保 base ∈ [0, MOD)
while (exponent > 0) {
if ((exponent & 1) == 1) { // 用位运算替代 %2，更高效
result = (result * base) % MOD; // ✅ 每次乘后立即对 long MOD 取模
}
base = (base * base) % MOD; // ✅ 同样保证不溢出
exponent >>= 1;
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
long result = solution.modPow(2L, 1_000_000_000L);
System.out.println(result); // 输出：336781474 ✅
}
}
? 注意事项总结：
-
永远使用
long MOD（如1_000_000_007L），而非int：防止int在混合运算中引发意外类型提升或截断； -
每次乘法后必须立即
% MOD：这是防止long溢出的唯一可靠手段（因a, b ，而 <code>MOD² = (1e9+7)² ≈ 1.000000014e18 ，故安全）； -
避免使用
BigInteger除非必要：虽然BigInteger.modPow()绝对精确且无溢出，但性能比long版本低 10–100 倍，竞赛/高频场景应优先优化long实现； -
输入预处理不可少：
base %= MOD可防止初始base过大（如base = MOD + 5）导致首轮乘法即溢出。
遵循以上原则，即可稳定、高效、准确地完成大数模幂运算——这也是 LeetCode 多道数学题（如 50. Pow(x, n)、剑指 Offer 16 等）的通用解法基石。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
