1

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

X = (a * X) / b;

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

我当然可以使用浮点运算，但是这个操作很有可能在没有浮点硬件的处理器上工作。

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

4

2 回答 2

4

You can rewrite it like this:

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

if you can be sure any of those doesn't overflow (the first is approximately result, the second is less than result, the third dividend approx b^2).

Why is that valid (provided no overflows occur, / means ordinary division, div integer division):

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

now, if we use this twice (with the C meaning of operators):

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

But I would recommend computing in a bigger precision, if that's possible

X = ((int)X*a)/b
于 2012-04-23T11:40:51.123 回答
3

您可以提升a为更大的数据类型，例如：

X = ((long)a * X) / b;
于 2012-04-23T11:44:32.917 回答