对于一个整数大小的bit数组中的非零 位统计的方法-bitcount [转]
对于一个整数大小的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中方法,
- iterated_popcnt (采用对每位进行移位来统计,效率低下)
- sparse_popcnt (采用数学特性进行处理,n&(n-1) 的方法来依次判断1的个数!循环次数=n中位为1的个数)
- dense_popcnt (sparse_popcnt的变种。当提前知道1的个数较多,可以采用取反的操作,减少1的个数,从而采用sparse_popcnt来提供效率)
- lookup_popcnt (该方法以空间换取时间的。将4字节的整数分为4个1字节char来看待,将256种char的bit1数目保存到表中,当计算n的位为1时,分为4个char,依次从表中直接读取1的位数,然后相加获取4字节空间中位为1的总数目)
- parallel_popcnt (不好说清,大家看来源文章)
- nifty_popcnt (不好说清,大家看来源文章)
- hacker_popcnt (不好说清,大家看来源文章)
- hakmem_popcnt (不好说清,大家看来源文章)
- assembly_popcnt (根据处理支持的popcount指令直接计算)