c++ - 解释了一种将 double 舍入为 32 位整数的快速方法

Question

在阅读 Lua 的源代码时，我注意到 Lua 使用宏将 double 值四舍五入为 32 位 int 值。该宏在Llimits.h header file中定义，内容如下:

union i_cast {double d; int i[2]};
#define double2int(i, d, t) \
    {volatile union i_cast u; u.d = (d) + 6755399441055744.0; \
    (i) = (t)u.i[ENDIANLOC];}

这里的ENDIANLOC是根据endianness定义的:0代表小端，1代表大端架构； Lua 小心地处理字节序。 t 参数被替换为整数类型，例如 int 或 unsigned int。

我做了一些研究，发现该宏有一种更简单的格式，它使用相同的技术:

#define double2int(i, d) \
    {double t = ((d) + 6755399441055744.0); i = *((int *)(&t));}

或者，在 C++ 风格中:

inline int double2int(double d)
{
    d += 6755399441055744.0;
    return reinterpret_cast<int&>(d);
}

这个技巧可以在任何使用 IEEE 754 的机器上运行(这意味着今天几乎每台机器)。它适用于正数和负数，并且四舍五入遵循 Banker’s Rule 。 (这并不奇怪，因为它遵循 IEEE 754。)

我写了一个小程序来测试它:

int main()
{
    double d = -12345678.9;
    int i;
    double2int(i, d)
    printf("%d\n", i);
    return 0;
}

它按预期输出-12345679。

我想详细了解这个棘手的宏是如何工作的。神奇的数字 6755399441055744.0 实际上是 2⁵¹ + 2⁵²，或 1.5 × 2⁵²，二进制为 1.5可以表示为 1.1。当任何 32 位整数与这个魔数(Magic Number)相加时——

好吧，我从这里迷路了。 这个技巧是如何工作的？

更新

1. 正如@Mysticial 所指出的，这种方法并不局限于32位的int，它还可以扩展为64位的int只要数字在 2⁵² 的范围内。 (虽然宏需要一些修改。)

2. 有些资料说这种方法不能用在Direct3D中。

3. 在使用 Microsoft assembler for x86 时，有一个用汇编代码编写的更快的宏(以下也是从 Lua 源代码中提取的):

    #define double2int(i,n)  __asm {__asm fld n   __asm fistp i}
   

4. 单精度数也有一个类似的魔数(Magic Number):1.5 × 2²³。

Answer 1

double 浮点类型的值表示如下:

可以看成是两个32位整数；现在，所有代码版本中的 int(假设它是 32 位 int)就是图中右侧的那个，所以你在做什么最后只取尾数的最低 32 位。

---

现在，到神奇的数字；如您所说，6755399441055744 是 2⁵¹ + 2⁵²；添加这样一个数字会强制 double 进入 2⁵² 和 2⁵³ 之间的“甜蜜范围”，如 explained by Wikipedia , 有一个有趣的性质:

Between 2⁵² = 4,503,599,627,370,496 and 2⁵³ = 9,007,199,254,740,992, the representable numbers are exactly the integers.

这是因为尾数是 52 位宽。

添加 2⁵¹ + 2⁵² 的另一个有趣的事实是，它只影响尾数的两个最高位——无论如何都会被丢弃，因为我们正在只有最低的 32 位。

---

最后但同样重要的是:标志。

IEEE 754 浮点使用幅度和符号表示，而“普通”机器上的整数使用 2 的补码算法；这里是怎么处理的？

我们只讨论了正整数；现在假设我们正在处理由 32 位 int 表示的范围内的负数，因此(绝对值)小于 (−2³¹ + 1)；称之为 -a。这样的数字显然是通过添加魔数(Magic Number)得到的，结果是 2⁵² + 2⁵¹ + (-a)。

现在，如果我们用 2 的补码表示来解释尾数，我们会得到什么？它必须是 (2⁵² + 2⁵¹) 和 (−a) 的 2 补码和的结果。同样，第一项仅影响高两位，位 0-50 中剩下的是 (-a) 的 2 的补码表示(同样，减去高两位)。

由于将 2 的补数减少到更小的宽度只是通过去除左侧的额外位来完成，因此取低 32 位可以正确地给出我们在 32 位 2 的补码算法中的 (-a)。