原创整理，转载请注明出处。
这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。
1．循环法（Iterated Count）
int bitcount (unsigned int n) {int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; }return count ;}最容易理解和想到的方法。对每一位依次判断是否为1，如果是就在count上加1。循环的次数是常数（n的位数）。在1比较稀疏的时候效率低，可用方法2改进。
2．Bit1稀疏 Sparse Ones
int bitcount (unsigned int n) {int count=0 ; while (n) { count++ ; n &= (n - 1) ; } return count ;}理解这个算法的核心，只需理解2个操作：
1> 当一个数被减1时，他最右边的那个值为1的Bit将变为0，同时其右边的所有的Bit都会变成1。
2>“&=”，位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.
这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1，循环几次。对Bit为1比较稀疏的数来说，性能很好。如：0x1000 0000, 循环一次就可以。
3．密集1的算法 Dense Ones
int bitcount (unsigned int n)
{
int count = 8 * sizeof(int) ;
n ^= (unsigned int) -1 ;
while (n)
{
count-- ;
n &= (n - 1) ;
}
return count ;
}
4．8bit静态表查找法 Precompute_8bit
static int bits_in_char [256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
6, 7, 6, 7, 7, 8
};
int bitcount (unsigned int n) { int count = 8 * sizeof(int) ; n ^= (unsigned int) -1 ; while (n) { count-- ; n &= (n - 1) ; } return count ; }
使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit 的n分4部分，直接在表中找到对应的Bit1的个数，然后求和。
这是最快的方法了。缺点是需要比较大的内存。
没有评论:
发表评论