小学期题用了这个函数，觉得十分高级，学习一个。
这个函数用来数二进制数中1的个数。正常的操作是：看unsigned int二进制表示下最右端是不是1；若是1，则计数器+1，再右移；重复32次。这样的操作需要进行32次int运算，效率不够高。这个问题可以二分解决。
首先看一个结论：对等长（含前导0）的二进制数$a$和$b$，设他们长为$k$，并记将$a$接在$b$前面形成的$2k$位的二进制数为$(a|b)$，那么$a+b=(a|b)>>k+(a|b)$。这是显而易见的。
这个操作将直接的加法转换为了位运算，当k较小时，可以将多个k拼在一起放在int32中，同时进行多个位运算。这样就有了提高加法效率的可能，相当于多线程了。然后，若k=1时将和用2位来存储，再取k=2，再将和用4位存储，再取k=4…然后就可以进行二分，在$O(\log n)$时间内求n个和。这是计算机的特性造就的性能提升。
下面模拟一下这个过程。现在有一个int8数n=01011100b。首先，对每一位，这一位本身的数字恰好记录了这一位上1的个数（这一位是1就有1个1，是0就有0个1）。接下来要将这些1加起来。首先取k=1，将n分为8位。然后相邻两位相加，此时每两位（指1-2,3-4这样的两位）共同构成的二进制数表示这两位上1的和。例如，(0|1|0|1|1|1|0|0)相邻两位相加后应为(01|01|10|00)。这个操作可以用刚刚的公式来进行。具体来讲，两位一格分为4格，每格里都是右移一位后相加，由于位运算可以同时进行，那么16格同时运算就应该是(n-偶数位-置0 + (n-奇数位-置0 >> 1))=((01|01|01|00)+(00|00|10|00)>>1)=(01|01|01|00)+(_0|00|01|00)=(01|01|10|00)，（奇、偶从右数起）此时每格里都完成了一次上述运算。接下来两位一份分为四份，相邻两份再次相加，即(01+01|10+00)=(0010|0010)。为了求和，要构造$2k$位的格子，于是四位一格分成2格，为(0101|1000)，求和过程应为(00|01|00|00)+(01|00|10|00)>>2=(00|01|00|00)+(00|01|00|10)=(0010|0010)。最后是0010+0010=(0000|0010)+(0010|0000)>>4=(0000|0010)+(0000|0010)=(0000|0100)=4，为n中1的个数，过程不再赘述。
唉，语言表达能力差，也不知道说清楚没。
最后给出代码。
1
2
3
4
5
6
7
8
9
| unsigned int popcount(unsigned int n)
{
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}
|
gcc内置了这个函数，名字是__builtin_popcount，当正常函数调用就行，即__builtin_popcount(n);。