缩放 64 位整数

• 下载源代码文件 - 29.2 Kb
• 下载演示项目 - 19.1 Kb

引言

是否曾经需要缩放64位整数？我在构建一个时间跟踪卡尔曼滤波器时需要。我决定像.NET框架那样，将时间保持为64位整数。使用64位整数的巨大优势在于，您可以保持时间高达100纳秒的精度，并在2012年之后保持这种精度。这大约是之后您无法再以微秒精度存储自1980年以来的秒数。另一个好处是易于与.NET交换时间。

因此，我使用__int64编写了所有时间跟踪。这进行得很顺利，因为VS C++编译器支持__int64的大多数算术运算。您可以进行加法、减法、乘法和除法，但所有这些都受限于结果必须适合__int64。问题出在我想要缩放时间值的时候。缩放的一般思想是将比例因子表示为分子和分母的商，然后先乘以分子，然后除以分母。您不能为此使用单独的乘法和除法，因为乘法的中间结果可能太大，无法容纳__int64。32位世界曾经存在这个问题，当时编译器还不支持64位整数。这就是为什么Windows提供了一个MulDiv函数，该函数一次调用即可完成乘法和除法，并跟踪64位中间结果。PC的32位处理器支持扩展的32位除法。不幸的是，操作系统没有提供一个函数来实现64位整数的相同功能。这可能是因为当今处理器上的div指令还不支持扩展的64位除法。

主要问题在于执行完整的64位MulDiv()所需的128位中间结果。在花费了大量时间在网上寻找一个现成的解决方案后，我发现了一些关于GNU MulDiv64的引用，它使用两个32位值缩放一个64位整数，以及Randall Hyde的著作“汇编编程艺术”。64*32/32的MulDiv可以解决问题，但并没有真正满足我寻找一个完整的64*64/64 MulDiv的搜索，该MulDiv可以让我只使用__int64。因此，我转向了Randall的书。这本书包含一节关于扩展精度整数算术的内容，这正是我所需要的。我将那里描述的方法实现到一个名为MulDiv64的小型C++库中。这样，您就不必经历将书中零散的知识拼凑起来和进行内联汇编编程的繁琐过程了。

MulDiv64库提供了两个函数

• __int64 _stdcall MulDiv64(__int64 operant, __int64 multiplier, __int64 divider)
• __int64 _stdcall MulShr64(__int64 operant, __int64 multiplier, unsigned char rshift)

在分母可以保持为2的幂的常量的情况下，可以使用右移来实现除法。这会使缩放速度大大加快，因为完整的128位除法由于缺乏硬件支持而有些缓慢。

使用代码

该库实现为一个C++静态库。这样可以避免在计算中出现DLL或COM开销。大部分功能是用内联汇编编写的，除了编译器可以高效处理的ABS()操作。我试图捕获处理器支持可以用来加速计算的特殊条件。例如，当分母足够小可以容纳DWORD时，除法可以分四块完成，而不是逐位完成。结果始终是128位值，但两个函数都会将结果裁剪为64位，因为这通常是您所需要的。

将库MulDiv64.lib包含在链接器输入的附加依赖项中。这可以在项目属性对话框中找到。别忘了也包含头文件。

使用该库的示例

#include "MulDiv64.h"

int _tmain(int argc, _TCHAR* argv[])
{
    __int64 r = 0;
    __int64 a = 0xaaaaaaaaaaaaaaaa;
    __int64 b = 0x5555555555555555;
    __int64 c = 0x1000000000000000;    // = 1 shl 60
    char s = 60;
    
    // This will return an incorrect result
    r = a * b / c;
    
    // This will return the correct result
    r = MulDiv64(a, b, c);
    
    // Because dividing by c can be expressed as a right shift
    // we can obtain the correct scaling faster with:
    r = MulShr64(a, b, s);
    
    return 0;
}

当然，代码也可以以多种其他方式导入。例如，将库编译为DLL或COM对象可能很方便。但这样使用会导致性能损失。

您会发现包含的测试程序稍微冗长一些，以便可以从命令行运行它。