浮点数快速取整算法 - 解读LUA中number2int函数源码

最近在看LUA源码时注意到这么一段有趣的代码。

/*
@@ lua_number2int is a macro to convert lua_Number to int.
@@ lua_number2integer is a macro to convert lua_Number to lua_Integer.
** CHANGE them if you know a faster way to convert a lua_Number to
** int (with any rounding method and without throwing errors) in your
** system. In Pentium machines, a naive typecast from double to int
** in C is extremely slow, so any alternative is worth trying.
*/

/* On a Pentium, resort to a trick */
#if defined(LUA_NUMBER_DOUBLE) && !defined(LUA_ANSI) && !defined(__SSE2__) && \
    (defined(__i386) || defined (_M_IX86) || defined(__i386__) || \
     defined(_M_X64) || defined(__x86_64__))

/* 32 windows system and microsoft compiler, use assembler */
#if defined(_WIN32) && !defined(_WIN64) && defined(_MSC_VER)

#define lua_number2int(i,d)   __asm fld d   __asm fistp i
#define lua_number2integer(i,n)     lua_number2int(i, n)

/* the next trick should work on any Pentium, but sometimes clashes
   with a DirectX idiosyncrasy on 32 windows system*/
#else

union luai_Cast { double l_d; int l_i; };
#define lua_number2int(i,d) \
  { volatile union luai_Cast u; u.l_d = (d) + 6755399441055744.0; (i) = u.l_i; }
#define lua_number2integer(i,n)     lua_number2int(i, n)

#endif

/* this option always works, but may be slow */
#else
#define lua_number2int(i,d) ((i)=(int)(d))
#define lua_number2integer(i,d) ((i)=(lua_Integer)(d))

#endif

/* }================================================================== */

在WIN32下lua_number2int函数中通过一些巧妙的方法来实现doubleint

浮点数

根据IEEE754描述,64位双精度类型浮点数表示方法各位作用如下

高位端 符号位 指数位 有效数字位 低位端
- 1 11 52 -
  • 符号位占用1bit,0表示正数,1表示负数。
  • 指数位由偏正值来表示,即用实际指数大小+1023来表示。
  • 有效数字位为从低位到高位开始表示的52个二进制位。

浮点数运算

浮点数运算大体分为三步

  1. 提升指数较小的数的指数,使其指数与大数相同,从而进行运算
  2. 将两个数的有效数字位相加,由于指数相同,相加完得到的数即为结果
  3. 对结果数值进行规格化操作

发现

根据上述浮点数表示方式和其加法运算,我们发现只需要对一个浮点数F加上它所能表示的最大的包含所有整数位的浮点数A,得到的结果的数值位就是原浮点数F的整数部分加上加数A的结果。而由于double类型的数值位有52位,已超出int类型读取范围。恰好在X86架构下,内存为小端对齐,此时联合luai_Cast中的int部分得到的刚好是double类型的数值位低32位的结果,即我们的加数A只要保证加法得到的结果有效数字位是以1为前导的,就不会因为规格化而影响到结果的低位。
在接下来的示例中,我们会发现使用2^52(最高位为10)作为加数的话,会导致负数取整时得到结果不是1为前导,从而由于规格化导致错位不能通过int字段读出正确的值。于是我们将第二高位也设置为1,得到1.5*2^52(最高位为11)作为加数,使得负数求和结果也永远是1为前导的。(Ps:事实上,从第33位到第52为全都为1也不会影响结果,因为超出了int的取值范围。即加数的要求为数量级为2^52,有效数字高两位为1,低32位为0,均可。)

示例

对(double)3.14取整

十进制 IEEE754 规格化二进制
3.14 0,1000000 0000,(1)1001 00011110 10111000 01010001 11101011 10000101 00011111
1.5 * 2^52 0,1000011 0011,(1)1000 00000000 00000000 00000000 00000000 00000000 00000000
十进制 指数位对齐二进制
3.14 0,1000011 0011,(0)0000 00000000 00000000 00000000 00000000 00000000 00000011
1.5 * 2^52 0,1000011 0011,(1)1000 00000000 00000000 00000000 00000000 00000000 00000000
Sum 0,1000011 0011,(1)1000 00000000 00000000 00000000 00000000 00000000 00000011

其中低32位结果为00000000 00000000 00000000 00000011,正是int3的补码二进制值(正数与原码相同)。至此,完成了3.14的快速取整。

对(double)-3.14取整

十进制 IEEE754 规格化二进制
-3.14 1,1000000 0000,(1)1001 00011110 10111000 01010001 11101011 10000101 00011111
1.5 * 2^52 0,1000011 0011,(1)1000 00000000 00000000 00000000 00000000 00000000 00000000
十进制 指数位对齐二进制
1.5 * 2^52 0,1000011 0011,(1)1000 00000000 00000000 00000000 00000000 00000000 00000000
3.14 0,1000011 0011,(0)0000 00000000 00000000 00000000 00000000 00000000 00000011
Minus 0,1000011 0011,(1)0111 11111111 11111111 11111111 11111111 11111111 11111100

其中低32位结果为11111111 11111111 11111111 11111100,正是int-3的补码二进制值(负数减一取反得到原码)。至此,完成了-3.14的快速取整。

所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。
本站部分内容收集于互联网,如果有侵权内容、不妥之处,请联系我们删除。敬请谅解!

添加新评论

  关于博主

  近期评论

  •  红小胖: 还是不可以 是为什么?
  •  Gill: 这个好玩。。。用了你的统计插件,我也发现有人扫,很不爽
  •  whc2001: 作者你好, 在新机器上运行似乎有bug, 会抛出异常"给定关键字不在字典中"...
  •  libcrypto: bomb 的原理是压缩后 1MB 解压后 1GB 的文件。因为在如果返回 gzip 类型的文件...
  •  天价萌: 额……现在爬站不都是异步的么……
  •  司空白: 您做的chorme的汇率插件最近一段时间连接不上了,可以抽空更新一下吗? 感谢大神
  •  风星璇: 说错了是现在还能不能监控别人的
  •  风星璇: 您好,请问剑三插件能支持监控自己的技能CD倒计时吗?
  •  小可可: 出酬劳,请帮忙给解决个问题!请联系我
  •  xiao酱沫: 重启机器,按住command+r进入恢复模式,打开终端输入csrutil disable 。然...

昆仑玄境山外山,乾坤阴阳有洞天。只问真君何处有,不向江湖寻剑仙。

长空令在,浩气长存。

玄剑化生雷霆势,镇我山河几度春。

万物皆虚幻,大道本无形。跳出三界外,不在五行中。

世人皆沉浸在纸醉金迷之中,往往要等到大祸临头或者一无所有才能幡然悔悟。凡事种种,皆是欲望使然。无欲则无悲无喜,恬淡自然。

以手中三尺长剑,镇四方八秒山河。

方才我喝了杯茶。