分类：
2008-05-15 22:58:35
Count the number of bits that are on in an unsigned integer（计算一个无符整数中1Bit的个数）-- (1)
计算一个无符号整数中有多少的Bit为1
原创整理，转载请注明出处。
这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。
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。这个算法循环的次数是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 ;
}
与2稀疏1的算法相类似。不同点是，针对1密集的情况，循环的次数会大大减少。他的循环次数：sizeof(int)-Bit 1的个数。
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)
{
// works only for 32-bit ints
return bits_in_char [n & 0xffu]
+ bits_in_char [(n >> 8) & 0xffu]
+ bits_in_char [(n >> 16) & 0xffu]
+ bits_in_char [(n >> 24) & 0xffu] ;
}
使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit 的n分4部分，直接在表中找到对应的Bit1的个数，然后求和。
这是最快的方法了。缺点是需要比较大的内存。
5．16bit静态表查找法Precompute_16bit
因为在计算64位int时，以上方法4并不总是最快，所以有以下的一个进化版，就是用十六Bit的表来作驱动映射。这样需要的内存就更大了。
static char bits_in_16bits [0x1u << 16] …;
int bitcount (unsigned int n)
{
// works only for 32-bit ints
return bits_in_16bits [n & 0xffffu]
+ bits_in_16bits [(n >> 16) & 0xffffu] ;
}
6. 合并计数器法 Parallel Counter
unsigned numbits(unsigned int i)
{
unsigned int const MASK1 = 0x55555555;
unsigned int const MASK2 = 0x33333333;
unsigned int const MASK4 = 0x0f0f0f0f;
unsigned int const MASK8 = 0x00ff00ff;
unsigned int const MASK16 = 0x0000ffff;
/*
MASK1 = 01010101010101010101010101010101
MASK2 = 00110011001100110011001100110011
MASK4 = 00001111000011110000111100001111
MASK8 = 00000000111111110000000011111111
MASK16 = 00000000000000001111111111111111
*/
i = (i&MASK1 ) + (i>>1 &MASK1 );
i = (i&MASK2 ) + (i>>2 &MASK2 );
i = (i&MASK4 ) + (i>>4 &MASK4 );
i = (i&MASK8 ) + (i>>8 &MASK8 );
i = (i&MASK16) + (i>>16&MASK16);
return i;
}
这个算法是一种合并计数器的策略。把输入数的32Bit当作32个计数器，代表每一位的1个数。然后合并相邻的2个“计数器”，使i成为16个计数器，每个计数器的值就是这2个Bit的1的个数；继续合并相邻的2个“计数器“，使i成为8个计数器，每个计数器的值就是4个Bit的1的个数。。依次类推，直到将i变成一个计数器，那么它的值就是32Bit的i中值为1的Bit的个数。
举个例子，假设输入的i值为10010111011111010101101110101111（十进制2541575087）
计算过程如下：（共22个1）
1. 将32个计数器合并为16个,每一个计数器代表 2-bit 的1个数
1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 = 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1
+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 = 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1
----------------------------------------------------------------------
1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10
2. 将16个计数器合并为8个,每一个计数器代表 4-bit 的1个数
1 1 1 2 1 1 1 2 = 01 01 01 10 01 01 01 10
+1 2 2 1 1 2 1 2 = 01 10 10 01 01 10 01 10
--------------- ---------------------------------------
2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100
3. 将8个计数器合并为4个,每一个计数器代表 8-bit 的1个数
3 3 3 4 = 0010 0011 0010 0010
+2 3 2 2 = 0011 0011 0011 0100
------- -----------------------------------
5 6 5 6 = 00000101 00000110 00000101 00000110
4. 将4个计数器合并为2个,每一个计数器代表 16-bit 的1个数
5 5 = 00000101 00000101
+ 6 6 = 00000110 00000110
----- ---------------------------------
11 11 = 0000000000001011 0000000000001011
5. 最后，将2个计数器合并为1个,每一个计数器代表 32-bit （也就是输入的值i）的1个数
11 = 0000000000001011
+11 = 0000000000001011
-- --------------------------------
22 = 00000000000000000000000000010110
对于该算法的实现，另外有一种比较好的写法，这种算法避免了使用常数宏，使比较通用的实现：
#define TWO(c) (0x1u << (c))
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
int bitcount (unsigned int n)
{
n = COUNT(n, 0) ;
n = COUNT(n, 1) ;
n = COUNT(n, 2) ;
n = COUNT(n, 3) ;
n = COUNT(n, 4) ;
/* n = COUNT(n, 5) ; for 64-bit integers */
return n ;
}
下面将讲解一些改进的算法。
7合并计数器法的优化
优化1：
算法的优化:基于以下两点合并计数器法可以进行优化：
1) 和的存储空间为 log2 (the number of bits being counted)*（coutern number）.随着（coutern number）减少，需要的存储bit减少。但是实际每次都被存储在一个32位整数。
2) 在多数架构中，简单的8-bit的常量比32-bit的更容易构造。
基于以上2点，最后的一步：
i = (i&MASK16) + (i>>16&MASK16)
可以变成：
i = (i + (i>>16))&MASK6;
MASK6是(1<<6)-1 or 0x1F,可以消除需要进行MASK16的操作。
经过这样的优化，可以节省两个操作：建立各大整数常量 和 一个与（AND）操作
unsigned numbits(unsigned int v)
{
unsigned int const MASK1 = 0x55555555;
unsigned int const MASK2 = 0x33333333;
unsigned int const MASK4 = 0x0f0f0f0f;
unsigned int const MASK6 = 0x0000003f;
unsigned int const w = (v & MASK1) + ((v >> 1) & MASK1);
unsigned int const x = (w & MASK2) + ((w >> 2) & MASK2);
unsigned int const y = (x + (x >> 4) & MASK4);
unsigned int const z = (y + (y >> 8));
unsigned int const c = (z + (z >> 16)) & MASK6;
return c;
}
举个例子，假设输入的i值为10010111011111010101101110101111（十进制2541575087）
计算过程如下：（共22个1）
1. 将32个计数器合并为16个,每一个计数器代表 2-bit 的1个数
1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 = 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1
+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 = 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1
----------------------------------------------------------------------
1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10
2. 将16个计数器合并为8个,每一个计数器代表 4-bit 的1个数
1 1 1 2 1 1 1 2 = 01 01 01 10 01 01 01 10
+1 2 2 1 1 2 1 2 = 01 10 10 01 01 10 01 10
--------------- ---------------------------------------
2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100
3. 将8个计数器合并为4个,每一个计数器代表 8-bit 的1个数：y = (x + (x >> 4) & MASK4)
0010 0011 0011 0011 0010 0011 0010 0100
+ 0000 0010 0011 0011 0011 0010 0011 0010
------- ---------------------------------------------------
0010 0101 0110 0110 0101 0101 0101 0110
&MASK4 0000 1111 0000 1111 0000 1111 0000 1111
------- --------------------------------------------------
0000 0101 0000 0110 0000 0101 0000 0110
4. 计算相邻的每对（只有2对,即4个Counter）8bit计数器的和（不进行合并计数器的操作）。
0000 0101 0000 0110 0000 0101 0000 0110
+ 0000 0000 0000 0101 0000 0110 0000 0101
----- ---------------------------------
0000 0101 0000 1011 0000 1011 0000 1011
5. 计算最后一对Counter(16BitCounter)的和，并根据掩码求出世纪的有效数字。其实将4，5步的与掩码运算合并为只进行一次。
0000 0101 0000 1011 0000 1011 0000 1011
0000 0000 0000 0000 0000 0101 0000 1011
-- --------------------------------
0000 0101 0000 1011 0001 0000 0001 0110
&MASK6 0000 0000 0000 0000 0000 0000 0011 1111
-- --------------------------------
0000 0000 0000 0000 0000 0000 0001 0110 = 22
优化2：
然而以上的算法，仍然可以优化为：这也许是最好的算法了。
unsigned numbits(unsigned int v)
{
unsigned int const MASK1 = 0x55555555;
unsigned int const MASK2 = 0x33333333;
unsigned int const MASK4 = 0x0f0f0f0f;
unsigned int const w = v - ((v >> 1) & MASK1);
unsigned int const x = (w & MASK2) + ((w >> 2) & MASK2);
unsigned int const y = (x + (x >> 4) & MASK4);
unsigned int const c = (y * 0x01010101) >> 24;
return c;
}
与优化1比较，又进行了以下两点优化：
1) 为了在第一行不使用AND操作，替换相邻位相加的操作为：v减去它的右移操作后与掩码操作的结果。这个结果以相同的。00 - 0 = 0, 01 - 0 = 01, 10 - 1 = 01, 11 - 1 = 10
即：
v= (v&MASK1 ) + (v>>1 &MASK1 );
w = v - ((v >> 1) & MASK1);
v=w
2) 为了合并最后两行，使用了一个乘法运算（00000001 00000001 00000001 00000001）和一个位移操作（只取最右边6位），这样的处理在一步就累加了4Bit大小的计数器。可以回忆乘法运算的竖式计算法，就是对第三步的结果Y,分为每8bit大小的四组，然后求和。
优化3：
还可以进行如下的优化：
#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}
请根据除法的意义思考为什么取255的余数。
8 MIT_HACKEMEM计数法MIT HACKMEM Count
int bitcount(unsigned int n)
{
/* works for 32-bit numbers only */
/* fix last line for 64-bit numbers */
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
这是一种很巧妙的算法：
考虑一个3Bit数N，可以看成4a+2b+c（a,b,c 为0 或者1）， 如果右移一位，得到2a+b,然后从原始的数（4a+2b+c）里减去2a+b，(N-N>>1)差为2a+b+c。如果右移两位，得到a, 然后用刚才得到的差2a+b+c减去a，(即(N-N>>1-N>>2)结果是a+b+c，这就是原始的数字里Bit为1的个 数。
这个算法如何实现呢？首先声明一个临时变量tmp。认为tmp是8进制描述的。8进制的每个数字都是n中相应的每3Bit位所描述的数字。最后返回这些8进制数的和就是我们需要的最终答案了。关键是，将相邻的8进制对加在一起，然后计算时记得对63(2的(3+3）次幂）-1)进行除运算取得余数。实现方法是：使用tmp右移3位、然后与自身相加，再与一个适当的掩码进行AND操作，产生一个数，这个数是相邻6位中含有Bit1的个数。
对64位数来说，应该比8进制数的多3倍（4倍），所以要对1023（64*（2的4次幂）-1）求模。(这算法在X11代码中被用到过。)
参考：