避免整数乘法和除法溢出

2022-01-17 00:00:00 algorithm numbers c c++

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

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.

如何有效地解决这个问题?直接的解决方案是将变量 ab 扩展为更大的整数类型,但可能没有更大的整数类型.有没有更好的方法来解决这个问题?

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?

推荐答案

如果没有更大的类型,你要么需要找一个 big-int 样式库,要么手动处理,使用长乘法.

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.

例如,假设 ab 是 16 位的.然后您可以将它们重写为 a = (1<<8)*aH + aLb = (1<<8)*bH + bL(其中所有单独的组件都是 8 位数字).那么你知道总体结果将是:

For instance, assume a and b are 16-bit. Then you can rewrite them as a = (1<<8)*aH + aL, and b = (1<<8)*bH + bL (where all the individual components are 8-bit numbers). Then you know that the overall result will be:

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

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

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.

相关文章