Ones Counting Algorithms
终于弄明白了一个巨ft无比的算法，聊以为记：
static UInt32 count_ones(UInt32 n)
{
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
return n;
}
另外一个更bt的，还是看不懂:(.
unsigned int ones32(register unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return (x & 0x0000003f);
}
=====下面是熊力的注释======
第一个算法的目的是计算出32位整形数字的二进制表示中有多少个一。最普通的算法是32次移位。这里给出的算法只需要做log2(32)，也就是5次移位就可以了。
算法思想是递归。思路是，首先把32位分割到32个盒子里面去，每个盒子一个数字，然后计算相邻两个盒子中有多少个一。然后相邻盒子之间合并，最后形成一个盒子。
第一次分割当然使用01010101
第二次就是001100110011
......
第二个算法，的思路跟第一个一模一样。只是每次合并和计算用的方法不同。第一个是移位，取掩码，相加。第二个计算前面可能会有溢出的时候用移位，取掩码，相减，到后面不可能溢出的时候直接移位相加。到了return的时候，由于32位数最多有0x20个1(10位二进制)，所以取10位个1作为掩码，就是0x3f
第二个算法在后面不可能溢出的时候省略了取掩码的过程，性能会更好。第一种算法非常容易理解
谢谢nickol:
0x3f是6个1，不是10个1，哈哈~
Outils 
Aide
