避免整数乘法溢出,然后除法

Question

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

怎么能有效地解决？直接的解决方案是扩展变量a或b更大的整数类型,但可能没有更大的整数类型.有没有更好的方法来解决这个问题？

Answer 1

如果没有更大的类型,您将需要找到一个big-int样式库,或者使用long multiplication手动处理它.

例如,假设a并且b是16位.然后你可以将它们重写为a = (1<<8)*aH + aL,并且b = (1<<8)*bH + bL(其中所有单个组件都是8位数字).然后你知道整体结果将是:

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

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