在整数乘法避免溢出其次师 [英] Avoiding overflow in integer multiplication followed by division

问题描述

我有两个不可或缺的变量 A 和 B 和恒定取值 RESP。 D 。我需要计算的值（A * B）＆GT;＆GT; S RESP。 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?

推荐答案

如果没有更大的类型，你要么需要找到一个大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 <<;＆LT; 8）*啊+铝和 B =（1 <<;＆LT; 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屋！