避免整数乘法和除法溢出
我有两个整数变量 a 和 b 和一个常量 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.
如何有效地解决这个问题?直接的解决方案是将变量 a 或 b 扩展为更大的整数类型，但可能没有更大的整数类型.有没有更好的方法来解决这个问题?
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.
例如，假设 a 和 b 是 16 位的.然后您可以将它们重写为 a = (1<<8)*aH + aL 和 b = (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.
相关文章