你和dalao之间，也许就差这么几个Magic Number了

当第一次看到某些Magic Number时的感觉是 * 这是什么？ * 这真的能正常工作么？ * 为什么会这样？ 这些数字看起来就像魔法一样，通过一种奇妙的方式，完成了一件不可能的事，所以也称它们为 magic number。 虽然在实践中它们未必全部都是实用的，甚至有些可以仅仅归结到有趣中，但其中体现的基础位运算、数值计算和一些基本数学思想是通用的。 ### 1、快速求平方根倒数 * magic number - 0x5f375a86 输入一个单精度浮点数 a 返回结果为 1 / sqrt(a) 比如输入 4.0 ，返回 0.499154 (准确值应是 0.5) 这段代码是编程界广为流传的一段奇妙代码，能估算出单精度浮点数的平方根倒数，它的速度是 cmath 中 1.0 / sqrt(a) 的三倍（当然，误差也更大）。这段代码的基础是牛顿迭代，最令人疑惑的是 0x5f375a86 - (ii >> 1) 这个语句，我们先把这个语句放在一边，过一遍基础流程。 ``` float r_sqrt(float a) { union { int ii; float i; }; //关于共用体union: //结构体的各个成员会占用不同的内存，互相之间没有影响；而共用体的所有成员共用同一段内存，修改一个成员会影响其余所有成员。 //共用体使用了内存覆盖技术，同一时刻只能保存一个成员的值，如果对新的成员赋值，就会把原来成员的值覆盖掉。 i = a; float ihalf = 0.5 * i; //这条语句目的是找到一个较好的 1 / sqrt(a) 的初始估算值，作为牛顿迭代的第一个值 ii = 0x5f375a86 - (ii >> 1); //第一次迭代 i = i * (1.5f - ihalf * i * i); //后续第二次、第三次迭代，实际上如果精度要求不高，一次迭代即可 //i = i * (1.5f - ihalf * i * i); //i = i * (1.5f - ihalf * i * i); return i; } ``` 对于想知道原理的OIer，强烈推荐这篇文章： [FAST INVERSE SQUARE ROOT](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) ### 2、奇偶性统计 大多数OIer使用的奇偶性统计： ``` int bits_parity(unsigned int a) { x^=x>>1; x^=x>>2; x^=x>>4; x^=x>>8; x^=x>>16; } ``` 其实还可以优化一下： * magic number - 0x6996 该函数返回 32 位二进制数中 1 的奇偶性。 返回 1 代表存在 奇数个 1，返回 0 代表存在 偶数个 1。 ``` unsigned int parity(unsigned int i) { /* * 每 8 位为一组，统结果存放在每组右侧 4 位元上 * i = 0x83d12312 / 10000011110100010010001100010010 * 此步完成后 i = xxxx1011xxxx1100xxxx0001xxxx0011 */ i = i ^ (i >> 4); /* * 每 16 位为一组，结果存放在每组右侧 4 位元上 * 此步完成后 i = xxxxxxxxxxxx0111xxxxxxxxxxxx0010 */ i = i ^ (i >> 8); /* * 每 16 位为一组，结果存放在每组右侧 4 位元上 * 此步完成后 i = xxxxxxxxxxxxxxxxxxxxxxxxxxxx0101 */ i = i ^ (i >> 16); /* * 0110100110010110 == 0x6996 * 合并i = i ^ (i >> 1)、i = i ^ (i >> 2)两步 */ return (0x6996 >> (i & 0xf)) & 0x1; } ``` ### 3、位元反序 首先说一下大多数OIer使用的反转，使用分治思想。 ``` unsigned int rev(unsigned int x) { x = (x & 0x55555555) << 1 | (x >> 1 & 0x55555555); x = (x & 0x33333333) << 2 | (x >> 2 & 0x33333333); x = (x & 0x0F0F0F0F) << 4 | (x >> 4 & 0x0F0F0F0F); x = (x & 0x00FF00FF) << 8 | (x >> 8 & 0x00FF00FF); x = (x & 0x0000FFFF) << 16 | (x >> 16 & 0x0000FFFF); return x; } ``` Donald E. Knuth 版位元反序算法， * magic number - 0x003f801f、0x01c003e0、0x0e038421、0x11c439ce、0x22488842、0x549556b5 这个算法通过精心设计的位移顺序和掩码实现了位元反序。 输入一个 32 位二进制数，返回 32 位二进制数，其位顺序和输入相反。 ``` //假设i = 01234567 89abcdef ghijklmn opqrstuv unsigned int revert(unsigned int i) { //循环左移 15 位 //fghijklm nopqrstu v0123456 789abcde i = i >> 17 | i << 15; /* * (i & 0x003f801f) << 10 => pqrstuv..........abcde.......... * (i & 0x01c003e0) => .......mno............56789..... * (i >> 10) & 0x003f801f => ..........fghijkl..........01234 * => pqrstuvm nofghijk labcde56 78901234 */ i = (i & 0x003f801f) << 10 | (i & 0x01c003e0) | ((i >> 10) & 0x003f801f); /* * (i & 0x0e038421) << 4 => tuv.......jkl....e....9....4.... * (i & 0x11c439ce) => ...s...mno...i....bcd..678..123. * (i >> 4) & 0x0e038421 => ....pqr.......fgh....a....5....0 * => tuvspqrm nojklifg hebcda96 78541230 */ i = (i & 0x0e038421) << 4 | (i & 0x11c439ce) | ((i >> 4) & 0x0e038421); /* * (i & 0x22488842) << 2 => v...r..o..l...h...d....8....3... * (i & 0x549556b5) => .u.s.q..n..k.i.g.e.c.a9.7.54.2.0 * (i >> 2) & 0x22488842 => ..t...p..m..j...f...b....6....1. * => vutsrqpo nmlkjihg fedcba98 76543210 */ i = (i & 0x22488842) << 2 | (i & 0x549556b5) | ((i >> 2) & 0x22488842); return i; } ```