如何正确执行modulo 10^9+7运算 解决整型乘法溢出问题

问题根因 #

原代码存在两处会触发错误的逻辑：

1. 两个int类型的差值直接做乘法时，运算全程以int类型执行，结果超出int取值范围后会发生截断溢出，得到错误值。此时再把错误的int结果赋值给long类型的res，已经无法恢复正确的乘积。
2. 最终返回时先对res做int强转再取模，如果res乘积本身超出int范围，强转步骤会再次触发溢出，进一步放大错误。

方案有效性判断 #

你编写的转换方案是该场景下的最优解，理由如下：

• 只要将任意一个乘数显式转为long，另一个乘数会自动隐式提升为long，整个乘法运算在long取值范围执行，完全规避int溢出问题。你写的两个操作数都显式转long的写法完全没问题，也可以简化为res = (long)(parts[1] - parts[0]) * (parts[3] - parts[2]);，效果完全一致。
• 仅涉及基础类型提升，几乎没有额外性能开销。
• 逻辑简单直白，可读性最高，不需要引入复杂的溢出判断逻辑。

最终返回逻辑优化 #

如果要保证最终结果完全正确，还需要调整返回时的执行顺序：先对long类型的res取模，再转int。因为模1000000007后的结果必然小于int的最大值（2^31-1），不会触发溢出。
如果需要保证模结果为非负值（差值可能为负的场景），可以再加一步符号修正，完整代码参考如下：

int m = 1000000007;
long res = 0L;
if(numOne > 3) {
  res = (long)(parts[1] - parts[0]) * (long)(parts[3] - parts[2]);
}
// 先取模再转int，可选符号修正
long modRes = res % m;
return (int)(modRes < 0 ? modRes + m : modRes);

内容的提问来源于stack exchange，提问作者anupamD