对于一个整数大小的bit数组中的非0 位统计的方法--bitcount [转]

对于bit数组中非0位个数统计的方法，请看以下文章

popcount 算法分析

http://www.cnblogs.com/Martinium/archive/2013/03/01/popcount.html

 

该方法的局限在于如果bit位超过64位则无法处理，仅用于unsigned int 的位计算。

如果对超过64/32bit的bit数组进行统计，则将bit区域按照sizeof(int)来切分，依次进行统计。

 

该文中提及到了 9中方法，

1. iterated_popcnt  （采用对每位进行移位来统计，效率低下）
2. sparse_popcnt     （采用数学特性进行处理，n&(n-1) 的方法来依次判断1的个数！循环次数=n中位为1的个数）
3. dense_popcnt      （sparse_popcnt的变种。当提前知道1的个数较多，可以采用取反的操作，减少1的个数，从而采用sparse_popcnt来提供效率）
4. lookup_popcnt      （该方法以空间换取时间的。将4字节的整数分为4个1字节char来看待，将256种char的bit1数目保存到表中，当计算n的位为1时，分为4个char，依次从表中直接读取1的位数，然后相加获取4字节空间中位为1的总数目）
5. parallel_popcnt     （不好说清，大家看来源文章）
6. nifty_popcnt           （不好说清，大家看来源文章）
7. hacker_popcnt        （不好说清，大家看来源文章）
8. hakmem_popcnt     （不好说清，大家看来源文章）
9. assembly_popcnt     (根据处理支持的popcount指令直接计算)