__builtin_popcount原理

小学期题用了这个函数, 觉得十分高级, 学习一个。

这个函数用来数二进制数中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的个数, 过程不再赘述。

唉, 语言表达能力差, 也不知道说清楚没。

最后给出代码。

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);。