避免整数乘法溢出，然后除法

我有两个积分变量a和b以及一个常数s resp。 d 。我需要计算(a*b)>>s resp的值。 a*b/d 。问题是乘法可能会溢出，即使a*b/d适合给定的整数类型，最终结果也不正确。

怎么能有效地解决？直接的解决方案是将变量a或b扩展为更大的整数类型，但可能没有更大的整数类型。有没有更好的方法来解决这个问题？

如果没有更大的类型，您将需要找到一个big-int样式库，或者使用long multiplication手动处理它。

例如，假设a和b是16位。然后你可以将它们重写为a = (1<<8)*aH + aL ，并且b = (1<<8)*bH + bL （其中所有单个分量都是8位数）。然后你知道整体结果将是：

 (a*b) = (1<<16)*aH*bH + (1<<8)*aH*bL + (1<<8)*aL*bH + aL*bL

这4个组件中的每一个都适合16位寄存器。您现在可以对每个组件执行例如右移，小心处理适当的进位。

如果较大的类型只是64位，则直接解决方案很可能会产生有效的代码。在x86 CPU上，两个32位数的任何乘法都会在另一个寄存器中产生溢出。因此，如果您的编译器理解它，它可以为Int64 result=(Int64)a*(Int64)b生成有效的代码。

我在C＃中遇到了同样的问题，编译器生成了相当不错的代码。 C ++编译器通常会创建比.net JIT更好的代码。

我建议将带有强制转换的代码编写到较大的类型中，然后检查生成的汇编代码以检查它是否良好。

我没有详尽地对此进行过测试，但是你能先做分工，然后考虑剩余部分，而不考虑额外的操作吗？由于d是2的幂，所有的除法可以简化为逐位运算。

例如，始终假设a > b （您希望先将较大的数字除以）。然后a * b / d = ((a / d) * b) + (((a % d) * b) / d)

在某些情况下（具有选定常数的历史LCG随机数生成器），对于a和d的某些值，可以执行您想要的操作。

这被称为Schrage的方法，参见例如。那里。