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

一名宅。 2017-07-10 AM 95℃ 0条

最近在看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的快速取整。

标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~