避免整数乘法和除法溢出 [英] Avoiding overflow in integer multiplication followed by division

问题描述

我有两个整数变量 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.

这篇关于避免整数乘法和除法溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！