如何重新缩放的（a * X）使用两个可能更大数量在C，看起来像这样的int/B式

Question

我有式：

X = (a * X)/b; 

这用于重新缩放X与a/b。但是X是16位无符号整数，并且与a相乘可能很容易溢出。我怎样才能用精确的结果使用整数进行计算。

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

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

Answer 1

您可以公关表参道a一个更大的数据类型，例如：

X = ((long)a * X)/b; 

Answer 2

你可以把它改写这样的：

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