c - 如何使用 (a*X)/b 公式中的两个可能更大的数字重新缩放 int

Question

我在 c 中有一个如下所示的公式:

X = (a * X) / b;

这用于用a/b 重新缩放X。但是 X 是 16 位无符号整数，与 a 的乘法很容易溢出。我如何才能仅使用具有准确结果的整数来进行此计算。

我当然可以使用浮点运算，但这种运算很有可能在没有浮点硬件的处理器上运行。

编辑:我忘了说 a 和 b 都是 32 位无符号整数。好吧，我的答案是右移 a 和 b 直到它们都适合 16 位。这样 a * X 最大为 32 位，最终计算是准确的。

Answer 1

你可以这样改写:

X = (a/b)*X + (a%b)*(X/b) + (a%b)*(X%b)/b

如果你能确定其中任何一个不会溢出(第一个大约是结果，第二个小于结果，第三个红利大约 b^2)。

为什么有效(前提是没有溢出，/表示普通除法，div整数除法):

X div Y =def floor(X/Y)
X =def (X div Y) * Y + X mod Y

(X*Y) div Z = floor(X*[(Y div Z) * Z + Y mod Z] / Z)
  = floor(X*(Y div Z)*Z/Z + X*(Y mod Z)/Z)
  = X*(Y div Z) + X*(Y mod Z) div Z

现在，如果我们使用它两次(使用运算符的 C 含义):

X = (a*X)/b = X*(a/b) + X*(a%b)/b =
            = X*(a/b) + (a%b)*(X/b) + (a%b)*(X%b)/b

但如果可能的话，我建议以更高的精度进行计算

X = ((int)X*a)/b