浮点数到整数的快速转换
之前在看 lua 源码的时候，看到⼀处浮点数转整数的⽅法，当时确实吓我⼀跳，后来在⽹上搜索了才知道浮点数原来还有这么神奇的地⽅，我看到⼀篇喜欢的⽂章，翻译⼀下（英⽂⼀般还请见谅），⼤家要闲着没事可以看看，先贴出 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.
*/
// 这是这个⽂件最trick的地⽅，把⼀个double数转换成long，⽤到了神奇的数字6755399441055744.0
/* On a Pentium, resort to a trick */
#if defined(LUA_NUMBER_DOUBLE) && !defined(LUA_ANSI) && !defined(__SSE2__) && (defined(__i386) || defined (_M_IX86) || defined(__i386__))
union luai_Cast { double l_d; long l_l; };
#define lua_number2int(i,d) { volatile union luai_Cast u; u.l_d = (d) + 6755399441055744.0; (i) = u.l_l; }
#define lua_number2integer(i,n) lua_number2int(i, n)
/* 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
上⾯⽤到了⼀个神奇的数字 6755399441055744.0，通过把⼀个 double 类型的数加上这个数字再直接拿来⽤就是整型了。这个真⼼让我惊奇。于是我马上在我的vs ⾥写了个测试了⼀下，结果同样令我⼼惊：
可以看到我⽤ 8.75 作为测试的 double 数，结果经过 lua 这个宏转换的结果是 9，其实当我把数改成 8.45 时，结果是 8，正好是转换成整数的结果。那么6755399441055744.0 这个神奇的数字到底是哪⾥来的呢？
我打开计算器看了⼀下，发现这个 6755399441055744.0 是 1.5 * 2^52，既然是这么个特殊的数，我们
知道在 IEEE 754 ⾥规定双精度浮点数是 64 位，⽽其中符号位占 1 位，指数部分是 11 位，那么尾数部分就是 52 位，那么这个 1.5 * 2^52 会不会跟这个有关呢？⽹上⼀搜看到篇⽂章，这⾥翻译了⼀下，有兴趣了解的朋友可以看看，我这⾥把⽂章的意思总结⼀下，⼤体意思就是说在做浮点数加减法的时候有这么⼏个步骤：
1、对阶
（就是使两个浮点数的两个指数部分相同，规定⼩数向⼤数对齐，因为如果是⼤数向⼩数对齐，那么就要左移⼤数的尾数部分，就有可能会丢失⼤数的最⾼有效位；⼩数向⼤数对齐是右移⼩数的尾数部分，⽽丢失⼩数的那点精度对结果来说是⽆关紧要的）
2、尾数相加
（为什么是相加⽽不是相加减，因为减法被转成加法做了，这个应该好理解，计算机⾥只有累加器）
3、对结果规格化
（这个可能⽐较⽣疏，其实也很好理解，就像我们⼗进制的科学记数法⼀样，我们规定尾数为 [1, 10) 之间的数,⼆进制⾥⾯我们如果尾数不是 1 开头，我们就移动成 1 开头，然后省去存 1，⽐如计算结果尾数为 0010，那么我就把尾数左移 3 位得到 1000，然后省去 1，只存 000，当然这个过程指数也会变）
4、舍⼊处理
（这个不多说，就那个意思）
下⾯来说这个 6755399441055744.0 的来历，我们利⽤的就是“对阶”的过程，如果我们把⼀个双精度浮点数加上 1.5 * 2^52，因为双精度浮点数的尾数部分正好是52 位，那么在进⾏对阶的时候，我们想要转换的浮点数如果⽐ 1.5 * 2^52 ⼩，那么就会向 1.5 * 2^52 对齐，对齐的⽅法我上⾯也说了，就是右移⼩数的尾数，⽽这⾥需要右移 52-⽬标数的指数位数，正好把⽬标数的所有⼩数部分全部移掉了，我们这⾥忽略舍⼊过程，只理解这个数的来源。那如果⽬标数⽐ 1.5 * 2^52 ⼤呢？呵呵，不⽤⽐ 6755399441055744.0 ⼤就会失败，为什么呢？因为我们这⾥的⽬的本来就是把 double 转换成 long，⽽ long 的范围是（32位
数）-2147483648 ~ 2147483647，远没有到 6755399441055744.0 这么⼤，所以这个转换的隐含条件还包括了⼀个 long 的范围在这⾥。其实根据这个⽅法看，只要求 long 的范围在 2^52 的规模以下就⾏。
为了更好的理解这个过程，我们来看⼀下这个转换的⼆进制的过程（这⾥的⼆进制表⽰没有对指数域做偏置，在标准 IEEE 中会进⾏偏置，想了解什么是偏置可以看看下⾯我翻译的那篇⽂章或者参考 IEEE 754 标准）：
的⼩数部分获得的。这个整数的规模有⼀部分是原实数的⼩数部分编码得到的最⼩有效位。这也是为什么这么多年来定点数作为实数系统的⼀个选择。⼀旦我们确定了范围，那么我就可以在只有极少数需要格外处理的情况下使⽤更快的整数操作。但是定点数在⼤多数情况下，有很多问题和⼀堆特殊情况需要处理，你必须⾮常⼩⼼的避免上溢和下溢的发⽣。⽽且这些以前所谓的更快速的整数操作在现在也没有浮点数操作快了。
浮点数运算是⼀件轻松的事情，它背后的主要思想是牺牲⼀些精度来换取数的范围。（意思就是说⽐如 64 位的浮点数，精度有 52 位，指数部分有 11 位，还有⼀位符号位）
现在，让我们忘掉浮点数，来想象⼀下我们有⼀个很巨⼤的⼆进制定点数，它有很多位整数部分和⼩数部分。⽐如有 1000 位整数部分，和 1000 位⼩数部分，所以我们可以表⽰⼀个数⼤到 2^1000 ⼩到 -2^1000。这个假想的定点数格式有⼀个巨⼤的范围和⼀个⾮常⾼的精度，范围的意思是能够表⽰的最⼤的数和最⼩的数的⽐值，精度的意思是有效数字的位数。所以，我们能够处理在我们模拟星系的系统中那些难以置信的⼤数，在保持星体间距离的准确性的同时我们也能够计算亚原⼦的半径。
但是，⼤多数应⽤并⾮是处处都需要这么⾼的精度。很多应⽤更多的是需要范围来表⽰巨⼤的值，⽐如星球之间的距离；或者是极⼩的值，⽐如原⼦之间的距离。但是通常不需要表⽰确切的数在处理两个不同规模的数的时候。
浮点数利⽤了这个精度和范围在使⽤上的差异，在存储的时候仅仅⽤了很少的⼏位就记录下了很⼤的范围（事实上甚⾄⽐我们假想的 2000 位定点数还要⼤）。浮点数通过把实数的指数和尾数分开存储来达到这个效果。就好像科学表⽰法⼀样，⼀个数⽐如 2.345*10^35 的尾数是 2.345，指数是 35（有时你也会看到不同的表⽰⽅式，但是他们都是等价的）。这个数只有 4 位精度，但是它的范围确实⾮常的⼤。
表⽰数值的精度同样是⼀件重要的事情。当指数是 35 时，改变第⼀位数字将按照 10^35 的规模来改变这个数，但是当指数为 0 时，改变第⼀位数字仅仅只按 1 的规模来改变。这个⽅法让你在处理“埃⽶”级别（纳⽶的⼗分之⼀）的规模的时候能够获得“埃⽶”级别的精确度，对于星系规模来说也是⼀样。
IEEE 浮点数标准规定了浮点数的表⽰⽅法以及如何操作浮点数。其中 IEEE 规定的浮点数格式中我们关⼼的只有两种：单精度浮点数和双精度浮点数。它们使⽤相同的转换⽅程来把⼆进制浮点数表⽰变成实数表⽰。你会发现它就像是⼀个⼆进制的科学记数法：
单精和双精这两种格式唯⼀不同的地⽅是上⾯这个格式中⼀些值的范围。所以我们接下来会按照顺序指出每个部分的不同点。
我们从上⾯格式的右⼿侧开始。尾数表⽰⽅法（1.mantissa）在第⼀次看的时候略显奇怪，但是当你意识到它是⼀个⼆进制数的时候时候就会觉得它清晰了⼀点。你同时也应该意识到这是⼀个规范的⼆进制数。“规范”在科学表⽰法⾥意思是尾数是⼤于等于 1 且⼩于 10（换句话说是⼀个不包括 0 的⼀位数）。这不是我想要的结果
我们上⾯那个科学表⽰法的例⼦ 2.345*10^35 就是规范的，⽽ 234500*10^30 就不规范。
⼀个规范的⼆进制数意思就是它会移动它的数位直到最⾼位为 1。仔细想想这个概念的意思。（001011 - > 1011）如果这个⼆进制数有前导 0，那么我们能够⽤指数的⼀部分来表⽰它们，就像我们在⼗进制科学记数法中所做的⼀样。因为最⾼位始终为 1，所以我们能够免去存储这个 1，把它作为我们这种表⽰法的⼀种默认
值就可以了。就像⼗进制科学记数法中保持尾数部分在 1 到 10 之间⼀样，⼆进制浮点数的尾数在 1 到 2 之间（⼤于等于 1 ⼩于 2）。
接下来，⼆进制指数的⼩数点是向左移还是向右移取决于指数是正还是负。这跟⼗进制科学记数法类似，当指数的⼩数点移动的时候，就补 0。指数域位数相同的浮点数⽐定点数有范围表⽰上的优势。其实定点数有⼀个隐含的⼩数点⽽它的所有位数其实都是指数，浮点数通过保存指数域来移动⼆进制⼩数点（这也就是浮点的意思）。如果⽤ 8 位来保存指数，那么⼀个 32 位数能够表⽰的范围就是 2^127 到 2^-127，⽽最好的定点数仅仅能表⽰ 2^32 到 0 和 2^16 到 2^-16 或者是 0 到2^-32，⽽且还不能同时表⽰这两个范围。当然，天下没有免费的午餐，32 位定点数⽐浮点数的精度更⾼，因为定点数有 32 位有效数字，⽽浮点数去掉指数部分后只有 24 位有效数字。
你会注意到 IEEE 标准中指数表达式实际上是⼀种指数的偏置。偏置的⽬的是使指数域的值始终为正。
换句话说，假设⼀个 8 位的指数，那么它偏置的值就是127，如果⼀个没有偏置的指数是 -126那么偏置后的指数为 1。同样的道理，⼀个偏置后指数域的值为 254，那么没有偏置的指数就是 127。全 0 和全 1 的指数值保留做⽆穷和 0 的指数值，当然我们没有⾜够的值去对应所有的特殊数。
最后，符号位（sign bit）的意思是这个数为正还是为负。不同于⼆进制补码的表⽰法，浮点数的正负仅仅由符号位决定。我们后⾯会谈到这样做的⽬的。表2 显⽰了单精度浮点数和双精度浮点数在 IEEE 规定的格式位数，Figure 1 显⽰了他们的是什么样的，最⾼有效位就是符号位。
⼀个例⼦
让我们来看⼀个例⼦，把⼀个⼗进制数转换成⼀个单精度⼆进制浮点数。我将⽤ 8.75 举例，因为它⽐较简单，甚⾄可以⽤⼿写来转换，但是它也能够展现⼀些复杂的地⽅。⾸先，我们将它变成⼀个⼆进制定点数—— 1000.11（⼩数的⼆进制转换⽅法），⼩数部分 .75 就是 2^-1 + 2^-2，所以是 .11。然后，我们把这个⼆进制数左移 3 位使它规格化，也就是 1.00011 * 2^3。最后，我们通过给指数加 127 来偏置指数，那么指数就是 130（10000010）。那么我们的浮点数尾数部分就是1.00011，当然，前置 1 是隐式的。我们的数是正的，所以符号位是 0。所以 8.75 最后的⼆进制浮点数的样⼦就如 Figure 2 所⽰，好了，现在我们已经熟悉了浮点数以及它的表⽰⽅法，接下来，我们可以学⼀些技巧了。
转换
毫不夸张的说，我注意到在某些处理器上浮点数转换成整数相当的慢。在奔腾处理器上，把浮点数转换成整数存下来的指令“FIST”（FIST 指令转换和舍⼊在堆栈顶 ST(0) 的源值为符号整数并复制它⾄规定的 16 位或 32 位内存单元。源可以是任⼀浮点数据类型，包括单精度、双精度或扩展的双精度浮点值。——引⾄《64位微处理器应⽤编程》）需要 6 个 CPU 周期，⽽乘法运算都仅仅只需要 3 个周期，这样你就明⽩我说的慢是什么意思了。更糟糕的是，FIST 指令同时占据浮点数通道和整数通道，所以其他的指令也没有办法执⾏。但是这⾥还有个选择，那就是我们动⽤我们学过的浮点数知识来写⼀个我们⾃⼰版本的 FIST，并且只需要⽤到普通的浮点数加法。
在做浮点数加法之前，CPU 需要对齐⼆进制⼩数点，⼩数点不对齐是没办法把尾数相加的。对齐的⽅法通常是左移较⼩的数的⼩数点。举例来说，如果我们想把两个⽤科学记数法表⽰的⼗进制数 2.345 * 10^35 和 1.0 * 10^32 相加，我们把较⼩的数的⼩数点左移 3 位来使他们达到同⼀个级别。然后再相加：2.345*10^35 + 0.001*10^35 = 2.346*10^35。⼆进制数跟这个道理是⼀样的。
我们能够利⽤这种对齐移动的⽅式来把浮点数位数表⽰弄的跟整数位数表⽰的⼀样，然后我们就可以像普通整数那样加了。理解这个的关键在于我们想要的整数已经存在于浮点数的位数中了，但是它被规范化了，所以移动它尾数部分的前导位，⽐如 8.75，就像 Figure 2 显⽰的那样。整数部分 8 是隐式的那⼀位加上尾数部分前⾯ 3 个 0 组成的。尾数部分接着的 11 是⼆进制 .75 的⼩数部分，等着转换成⼀个定点数。
想象⼀下当你把 2 个浮点数相加时，⽐如 2^8 = 256 加到 8.75，如 Figure 3。为了做这个加法，因为指数不相同，所以 CPU 会左移 5 位 8.75 的⼆进制⼩数点（8 - 3 = 5）。加法把 256 隐含的那⼀位加到了⼩数点对齐之后的 8.75 中，然后当结果做了规范化之后，在 256 中隐含的那⼀位仍然是隐含的，所以 8.75 就下移了。你在 Figure 3 的结果尾数部分可以看到 8.75。那当我加 233 时呢，或者加跟尾数的宽度⼀样⼤的数呢？就像你想的那样，8.75 的尾数会移动 23 - 3 = 20 位，只留下1000，这个的值是 8（因为 .75 被我们移除掉了，单精度浮点数的尾数只有 23 位，虽然这个时候舍⼊模式就会⽣效，但是为了简化，我们这⾥假设舍⼊为0）。如果我们盖住符号位和指数部分，直接读尾数部分，那么我们就得到了把 8.75 转换成整数的结果 8。
这个技巧只对正数有效，如果你尝试把⼀个负数转换过来就会发现出错了。你可以通过⾃⼰⼿动操作移位来看看为什么会出错。我发现两个正数相减⽐⼀正数⼀负数相加要容易。⽐如计算 2^23 + (-8.75)，⽽ 2^23 - 8.75 要容易⼀些。这是由于符号位的表⽰⽅法导致的（⽤⼀张纸⼀⽀笔你可以看得更加清楚）。所以，当你在做减法的对齐的时候，8.75 减去⼀个⼤的尾数，如果所有位都为 0 了，就会从那个隐含的位借⼀。这个最初看起来不错，尾数是正确值 -8.75，但是执⾏规范化步骤之后，整个数就乱了，因为我们从隐含位借了 1，那么这个隐含位就不再是最⾼有效位了，所以规范化的操作移动整个数之后，这个数就乱了。
但是，等等，好像并⾮全乱了。我们需要的其实只是⼀位尾数让我们可以借位罢了，这样我们那个隐含
位仍然保留并正确移动。我们可以通过乘以 1.5 来实现这个多出的⼀位，1.5 在⼆进制中是 1.1，那么第⼀个 1 就成为隐含位，第⼆个 1 就变成了尾数的最⾼有效位拿来借位。这样，⽆论是正数还是负数的规范化操作都能够正确的进⾏了。负数就在最⾼位加 1 来完成⼆进制补码的表⽰。
够正确的进⾏了。负数就在最⾼位加 1 来完成⼆进制补码的表⽰。
当你仅处理⼀两个正数和负数时，计算掩码已经够⿇烦了，更别谈你想要透明的进⾏这种处理，计算如何使⽤掩码对于⾼位数来说⾮常缓慢。但是，这⾥也有⼀个⼩技巧。如果你把这个浮点数减去我们刚刚⽤上⾯转换成整数⽅法得到的那个整数，那么就会正确的移除掉所有的⾼位，正数就置 0，负数就置 1。
你会发现这个技巧只使⽤到了 32 位中的⼀部分，因为还有指数部分和符号位。并且当我们使⽤“1.5”的⼩技巧时，我们还会失去额外的⼀位来确保正数和负数同样适⽤。但是，我们可以通过使⽤⼀个双精度数来作为暂时的转换这样就可以避免范围问题和掩码问题。如果我们做加法时把我们的数当作⼀个双精度类型（确保在做整数转换时加的值是 1.5 * 2^52）并且只读取最低的 32 位有效数字作为整数，我们就得到了⼀个 32 位精度的数并且不需要使⽤掩码。因为指数部分和符号位移到了双精度值的第⼆个 32 位中。
总之，在做整数转换时我们可以通过加⼀个⼤数来控制怎么去移动对齐。我们⼀直移位直到只保留整数
部分，或者可以移动⼀定值保留⼀定的⼩数精度。
使⽤这些技巧看起来确实⿇烦，但是在⼀些处理器上，像 X86 系列，这会带来很⼤的不同。在奔腾处理器上使⽤ FIST 指令，你需要 6 个 CPU 周期，在此之间你⽆法执⾏任何其他的指令。但是使⽤这个加法的技巧，你就可以节省出 3 个周期来进⾏别的整数指令的运⾏。你同时能够控制有多少位⼩数精度⽽不是⼀味的全部转换成整数。
你的观点呢？
在我做总结之前，我想告诉你⼀些别的技巧，来供你做判断做不做这些改变。对指数做偏置是因为这样在做两个数的⽐较的时候更加⽅便。指数永远是正的，这样⼀个⼤数⽐⼀个⼩数要⼤在⽐较指数部分的时候就已经确定了。符号位的存在导致⽐较更加⿇烦，但是单符号值却没有问题。当然，你可以移除符号位来取得浮点数的绝对值。
我已经⾮常接近最酷的技巧了，这个技巧就是在做坑爹的除法的时候重叠整数指令的运⾏。但是我没有深⼊探讨这个话题，这个就要等到下⼀次了。
最后作者推荐了⼀些读物：
The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (Addison-Wesley, 1981) by D.Kn
uth
Graphics Gems series from AP Professional
发布评论