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

2018-02-04 13:30:42


当第一次看到某些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

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;
}