几个比较神奇的函数

之前看极课时间的公开课，其中有几个函数个人觉得比较牛，在这里分享一波
1. 一次牛顿迭代求平方根
这个不想多谈，神奇的常数，存储转换都用到了。。。

float Q_rsqrt( float number )

{

long i;

float x2, y;

const float threehalfs = 1.5F;

x2 = number * 0.5F;

y = number;

i = * ( long * ) &y; // evil floating point bit level hacking

i = 0x5f3759df - ( i >> 1 ); // what the fuck?

y = * ( float * ) &i;

y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration

// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

#ifndef Q3_VM

#ifdef __linux__

assert( !isnan(y) ); // bk010122 - FPE?

#endif

#endif

return y;

}

2. 常数时间复杂度求整数二进制表示当中1的个数
这个可以简单说下，相当于从左到右依次2、4、8、16分割，然后每组求和，最终的出结果

int count_ones(int x){
    x = (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1);
    x = (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2);
    x = (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4);
    x = (x & 0x00FF00FF) + ((x & 0xFF00FF00) >> 8);
    x = (x & 0x0000FFFF) + ((x & 0xFFFF0000) >> 16);
    return x;
}

3. 求一个整数，二进制表示当中，是1的最低有效位（也就是末尾连续0的数量）
这个我是只能想到(x-1)^x&x，然后查表即可，这里利用了取反（负数二进制补码表示）然后用到了De Bruijn序列、汉密尔顿回路、欧拉回路。。。。

unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

路还很长，各位公勉～