避免整数乘法和除法溢出
我有两个整数变量 a 和 b 以及一个常量 s 。 d。我需要计算 (a*b)>>s 的值。 a*b/d。问题是乘法可能会溢出，即使 a*b/d 可以适合给定的整数类型，最终结果也不会正确。
如何有效解决这个问题？最直接的解决方案是将变量 a 或 b 扩展为更大的整型，但可能不存在更大的整型。有没有更好的方法来解决问题呢？
I have two integral variables a and b and a constant s resp. d. I need to calculate the value of (a*b)>>s resp. a*b/d. The problem is that the multiplication may overflow and the final result will not be correct even though a*b/d could fit in the given integral type.
How could that be solved efficiently? The straightforward solution is to expand the variable a or b to a larger integral type, but there may not be a larger integral type. Is there any better way to solve the problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果没有更大的类型，您要么需要找到一个 big-int 样式库，要么使用长乘法手动处理它。
例如，假设
a和b是 16 位。然后您可以将它们重写为a = (1<<8)*aH + aL和b = (1<<8)*bH + bL（其中所有单独的组件都是 8 位数字）。那么您就知道总体结果将是：这 4 个组件中的每一个都适合一个 16 位寄存器。现在，您可以对每个单独的组件执行右移操作，并小心地适当处理进位。
If there isn't a larger type, you will either need to find a big-int style library, or deal with it manually, using long multiplication.
For instance, assume
aandbare 16-bit. Then you can rewrite them asa = (1<<8)*aH + aL, andb = (1<<8)*bH + bL(where all the individual components are 8-bit numbers). Then you know that the overall result will be:Each of these 4 components will fit a 16-bit register. You can now perform e.g. right-shifts on each of the individual components, being careful to deal with carries appropriately.
我还没有对此进行详尽的测试，但是您可以先进行除法，然后以额外的操作为代价计算余数吗？由于 d 是 2 的幂，因此所有除法都可以简化为按位运算。
例如，始终假设
a > b（您想先除较大的数字）。然后a * b / d=((a / d) * b) + (((a % d) * b) / d)I haven't exhaustively tested this, but could you do the division first, then account for the remainder, at the expense of extra operations? Since
dis a power of two, all the divisions can be reduced to bitwise operations.For example, always assume
a > b(you want to divide the larger number first). Thena * b / d=((a / d) * b) + (((a % d) * b) / d)如果较大的类型只有 64 位，那么直接的解决方案很可能会产生高效的代码。在 x86 CPU 上，两个 32 位数字的任何乘法都会导致另一个寄存器溢出。因此，如果您的编译器理解这一点，它就可以为
Int64 result=(Int64)a*(Int64)b生成高效的代码。我在 C# 中遇到了同样的问题，编译器生成了非常好的代码。 C++ 编译器通常会创建比 .net JIT 更好的代码。
我建议编写带有较大类型转换的代码，然后检查生成的汇编代码以检查其是否良好。
If the larger type is just 64 bits then the straight forward solution will most likely result in efficient code. On x86 CPUs any multiplication of two 32 bit numbers will give the overflow in another register. So if your compiler understands that, it can generate efficient code for
Int64 result=(Int64)a*(Int64)b.I had the same problem in C#, and the compiler generated pretty good code. And C++ compilers typically create better code than the .net JIT.
I recommend writing the code with the casts to the larger types and then inspect the generated assembly code to check if it's good.
在某些情况下（历史上具有选定常数的 LCG 随机数生成器），对于 a 和 d 的某些值，可以执行您想要的操作。
这称为 Schrage 方法，参见例如。 那里。
In certain cases (historically LCG random number generators with selected constants), it is possible to do what you want, for some values of a and d.
This is called Schrage's method, see eg. there.