避免整数乘法和除法溢出

Question

我有两个积分变量

a

和

b

以及一个常数

s

。

d

。我需要计算

(a*b)>>s

的值。

a*b/d

。问题是乘法可能会溢出，即使

a*b/d

可以适合给定的整数类型，最终结果也不会正确。

如何有效解决这个问题？最直接的解决方案是将变量

a

或

b

扩展为更大的整数类型，但可能不存在更大的整数类型。有没有更好的办法解决这个问题？

Answer 1

如果没有更大的类型，您要么需要找到一个big-int样式库，要么使用长乘法手动处理它。

例如，假设

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 位寄存器。您现在可以执行例如对每个单独的组件进行右移，小心适当地处理进位。

Answer 2

我还没有对此进行详尽的测试，但是您可以先进行除法，然后计算余数，但需要进行额外的操作吗？由于

d

是 2 的幂，因此所有除法都可以简化为按位运算。

例如，始终假设

a > b

（您想先除较大的数）。然后

a * b / d

=

((a / d) * b) + (((a % d) * b) / d)

Answer 3

如果较大的类型只有 64 位，那么直接的解决方案很可能会产生高效的代码。在 x86 CPU 上，两个 32 位数字的任何乘法都会导致另一个寄存器溢出。因此，如果您的编译器理解这一点，它就可以为

Int64 result=(Int64)a*(Int64)b

生成高效的代码。

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

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

Answer 4

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

这称为 Schrage 方法，请参见示例。 那里。