解释了将double转换为32位int的快速方法
Yu *_*Hao 169 c c++ floating-point performance
在阅读Lua的源代码时,我注意到Lua使用a将a macro舍入double到32位int.我解压缩了macro,它看起来像这样:
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对于little endian,1对于big endian.Lua小心翼翼地处理字节序.t代表整数类型,如int或unsigned int.
我做了一些研究,并且有一个更简单的格式macro使用相同的想法:
#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规则.(这并不令人惊讶,因为它遵循IEEE 754.)
我写了一个小程序来测试它:
int main()
{
double d = -12345678.9;
int i;
double2int(i, d)
printf("%d\n", i);
return 0;
}
正如预期的那样输出-12345679.
我想详细说明这个棘手的macro工作原理.幻数6755399441055744.0实际上是2^51 + 2^52,或者1.5 * 2^52,1.5二进制可以表示为1.1.当任何32位整数被添加到这个神奇数字时,好吧,我从这里迷路了.这个技巧如何运作？
PS:这是Lua源代码,Llimits.h.
更新:
- 正如@Mysticial指出的那样,这种方法并不局限于32位
int,int只要数量在2 ^ 52的范围内,它也可以扩展到64位.(macro需要一些修改.) - 有些资料称这种方法不能用于Direct3D.
使用Microsoft汇编程序for x86时,
macro写入速度更快assembly(这也是从Lua源代码中提取的):
Run Code Online (Sandbox Code Playgroud)#define double2int(i,n) __asm {__asm fld n __asm fistp i}单精度数有一个类似的幻数:
1.5 * 2 ^23
Mat*_*lia 160
A double表示如下:
它可以看作是两个32位整数; 现在,int代码的所有版本(假设它是32位int)都是图中右边的那个版本,所以你最后做的只是采用最低32位的尾数.
现在,到神奇的数字; 正如你所说,6755399441055744是2 ^ 51 + 2 ^ 52; 添加这样一个数字迫使它double进入2 ^ 52和2 ^ 53之间的"甜蜜范围",正如维基百科在这里解释的那样,它具有一个有趣的特性:
在2 52 = 4,503,599,627,370,496和2 53 = 9,007,199,254,740,992之间,可表示的数字正好是整数
这是因为尾数是52位宽.
关于添加2 51 +2 52的另一个有趣的事实是它仅在两个最高位中影响尾数 - 无论如何它们都被丢弃,因为我们只取其最低的32位.
最后但并非最不重要的:标志.
IEEE 754浮点使用幅度和符号表示,而"普通"机器上的整数使用2的补码算法; 这是怎么处理的？
我们只讨论了正整数; 现在假设我们正在处理32位表示的负数int,所以(绝对值)小于(-2 ^ 31 + 1); 叫它-a.通过添加幻数,这样的数字显然是正数,结果值是2 52 +2 51 +( - a).
现在,如果我们用2的补码表示来解释尾数,我们会得到什么？它必须是2的补码和(2 52 +2 51)和(-a)的结果.同样,第一项仅影响高两位,位0~50中保留的是(-a)的2的补码表示(再次,减去高两位).
由于将2的补码数减少到较小的宽度只是通过切掉左边的额外位来实现,所以采用较低的32位可以正确地给出(-a)32位,2的补码算法.
- 对于那些想要转换为 `int64_t` 的人，你可以通过将尾数左移然后右移 13 位来实现。这将从“魔术”数字中清除指数和两位，但会保留符号并将其传播到整个 64 位有符号整数。`联合{双d; int64_t l; } 魔法; magic.d = 输入 + 6755399441055744.0；魔法.l <<= 13; 魔法.l >>= 13;` (3认同)
这种“技巧”来自较旧的 x86 处理器，使用 8087 指令/接口进行浮点运算。在这些机器上，有一条将浮点转换为整数“拳头”的指令，但它使用当前的 fp 舍入模式。不幸的是，C 规范要求 fp->int 转换向零截断，而所有其他 fp 操作都舍入到最接近的值，因此进行
fp->int 转换需要首先更改 fp 舍入模式，然后执行拳头操作，然后恢复 fp舍入模式。
现在，在最初的 8086/8087 上，这还不算太糟糕，但在后来开始获得超标量和无序执行的处理器上，改变 fp 舍入模式通常会序列化 CPU 内核，并且成本相当昂贵。因此，在像 Pentium-III 或 Pentium-IV 这样的 CPU 上，总体成本相当高——普通的 fp->int 转换比这种 add+store+load 技巧贵 10 倍或更贵。
然而，在 x86-64 上，浮点是通过 xmm 指令完成的，并且转换
fp->int 的成本非常小，因此这种“优化”可能比正常转换慢。