Tar*_*ron 13 c++ math bit-manipulation integer-overflow integer-division
我的程序经常需要执行以下计算：
鉴于：
找：
显然我可以直接使用r=x*n/d，但经常会从中溢出x*n。如果我改为这样做，r=x*(n/d)则由于整数除法会除去小数部分，因此我只会得到0或x。然后有，r=x*(float(n)/d)但在这种情况下我不能使用浮点数。
精度会很高，但并不像速度和决定性功能那么关键（总是在给定相同输入的情况下返回相同的值）。
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的特定情况下，我使用了移位而不是乘法，但这并没有太大帮助。
我现在已经对几种可能的解决方案进行了基准测试，包括来自其他来源的奇怪/聪明的解决方案，例如组合 32 位 div & mod & add 或使用农民数学，以下是我的结论：
首先，如果您仅针对 Windows 并使用 VSC++，则只需使用 MulDiv()。它相当快（比在我的测试中直接使用 64 位变量更快），同时仍然准确并为您舍入结果。即使考虑到诸如 unsigned-only 和 N <= D 之类的限制，我也找不到任何更好的方法在 Windows 上使用 VSC++ 执行此类操作。
然而，就我而言，即使跨平台，拥有具有确定性结果的函数甚至比速度更重要。在我用作测试的另一个平台上，使用 32 位库时，64 位除法比 32 位慢得多，并且没有 MulDiv() 可供使用。该平台上的 64 位除法大约需要 32 位除法的 26 倍（但 64 位乘法与 32 位版本一样快......）。
因此，如果您有像我这样的情况，我将分享我得到的最佳结果，结果证明这只是 chux 答案的优化。
我将在下面分享的两种方法都使用以下函数（尽管特定于编译器的内在函数实际上仅有助于提高 Windows 中 MSVC 的速度）：
inline u32 bitsRequired(u32 val)
{
#ifdef _MSC_VER
DWORD r = 0;
_BitScanReverse(&r, val | 1);
return r+1;
#elif defined(__GNUC__) || defined(__clang__)
return 32 - __builtin_clz(val | 1);
#else
int r = 1;
while (val >>= 1) ++r;
return r;
#endif
}
现在，如果 x 是一个 16 位或更小的常量，并且您可以预先计算所需的位，我发现此函数在速度和准确性方面取得了最佳结果：
u32 multConstByPropFrac(u32 x, u32 nMaxBits, u32 n, u32 d)
{
//assert(nMaxBits == 32 - bitsRequired(x));
//assert(n <= d);
const int bitShift = bitsRequired(n) - nMaxBits;
if( bitShift > 0 )
{
n >>= bitShift;
d >>= bitShift;
}
// Remove the + d/2 part if don't need rounding
return (x * n + d/2) / d;
}
在具有慢速 64 位除法的平台上，上述函数的运行速度约为 16.75 倍return ((u64)x * n + d/2) / d;，平均准确度为 99.999981%（比较返回值与预期 x 范围的差异，即，当当使用大约一百万个随机输入进行测试时，x 是 2048 将是 100 - (1/2048 * 100) = 99.95% 准确度，其中大约一半通常是溢出。最坏情况下的准确率为 99.951172%。
对于一般用例，我从以下内容中找到了最佳结果（并且不需要限制 N <= D 来启动！）：
u32 scaleToFraction(u32 x, u32 n, u32 d)
{
u32 bits = bitsRequired(x);
int bitShift = bits - 16;
if( bitShift < 0 ) bitShift = 0;
int sh = bitShift;
x >>= bitShift;
bits = bitsRequired(n);
bitShift = bits - 16;
if( bitShift < 0 ) bitShift = 0;
sh += bitShift;
n >>= bitShift;
bits = bitsRequired(d);
bitShift = bits - 16;
if( bitShift < 0 ) bitShift = 0;
sh -= bitShift;
d >>= bitShift;
// Remove the + d/2 part if don't need rounding
u32 r = (x * n + d/2) / d;
if( sh < 0 )
r >>= (-sh);
else //if( sh > 0 )
r <<= sh;
return r;
}
在 64 位除法速度较慢的平台上，上述函数的运行速度比使用 64 位变量快约 18.5 倍，平均准确率为 99.999426%，最坏情况准确率为 99.947479%。
我能够通过扰乱移位来获得更快的速度或更高的精度，例如如果不是绝对必要的话，尝试不一直向下移位到 16 位，但任何速度的提高都会以精度方面的高昂代价为代价反之亦然。
我测试的其他方法都没有达到相同的速度或精度，大多数都比仅使用 64 位方法慢或精度损失巨大，因此不值得讨论。
显然，不能保证其他人会在其他平台上获得类似的结果！
编辑：用纯代码替换了一些麻烦的黑客，这些代码实际上通过让编译器完成其工作而运行得更快。