c++ - 将整数乘以适当分数的快速方法，无需 float 或溢出

Question

我的程序经常需要执行以下计算:

给定:

• N 是一个 32 位整数
• D 是一个 32 位整数
• abs(N) <= abs(D)
• D != 0
• X 是任意值的 32 位整数

查找:

• X * N/D 作为一个舍入整数，X 缩放为 N/D(即 10 * 2/3 = 7)

显然我可以直接使用 r=x*n/d，但我经常会从 x*n 得到溢出。如果我改为执行 r=x*(n/d) ，那么我只会得到 0 或 x，因为整数除法会丢弃小数部分。然后是 r=x*(float(n)/d) 但在这种情况下我不能使用 float 。

准确度会很好，但不如速度和确定性函数重要(在相同的输入下总是返回相同的值)。

N 和 D 目前已签名，但如果有帮助，我可以解决它们始终未签名的问题。

适用于任何 X 值(以及 N 和 D，只要 N <= D)的通用函数是理想的，因为此操作以各种不同的方式使用，但我也有一个特定情况，其中 X 的值是 2 的已知恒定幂(准确地说是 2048 年)，只要加快特定调用的速度就会有很大帮助。

目前我正在使用 64 位乘除法来避免溢出(本质上是 int multByProperFraction(int x, int n, int d) { return (__int64)x * n/d; } 但有一些断言和额外的位摆弄以进行舍入而不是截断)。

不幸的是，我的分析器报告 64 位除法函数占用了太多 CPU(这是一个 32 位应用程序)。我试图减少我需要进行此计算的频率，但我已经没有办法解决它了，所以我试图找出一种更快的方法，如果它甚至可能的话。在 X 是常数 2048 的特定情况下，我使用位移而不是乘法，但这并没有多大帮助。

Answer 1

容忍不精确并使用 n,d,x

的 16 MSBits

Algorithm
while (|n| > 0xffff) n/2, sh++
while (|x| > 0xffff) x/2, sh++
while (|d| > 0xffff) d/2, sh--
r = n*x/d  // A 16x16 to 32 multiply followed by a 32/16-bit divide.
shift r by sh.

当 64 位 除法成本很高时，这里的前/后处理可能值得进行 32 位除法 - 这肯定是 CPU 的一大块。

如果无法哄骗编译器进行 32 位/16 位除法，则跳过 while (|d| > 0xffff) d/2, sh-- 步骤并执行32/32 除数。

尽可能使用无符号数学。