### Count the number of bits that are on in an unsigned integer（计算一个无符整数中1Bit的个数）-- (1)

1．循环法（Iterated Count

`int bitcount (unsigned int n)  `
`{`
`int count=0;    `
`    while (n)  {`
`      count += n & 0x1u ;`
`      n >>= 1 ;`
`    }`
`return count ;`
`}`

2Bit1稀疏Sparse Ones

`int bitcount (unsigned int n)  `
`{`
`int count=0 ;`
`       while (n)  {`
`       count++ ;`
`       n &= (n - 1) ;`
`   }`
`   return count ;`
`}`

1> 当一个数被减1时，他最右边的那个值为1Bit将变为0，同时其右边的所有的Bit都会变成1
2>“&=”，位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.

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的个数。

48bit静态表查找法 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] ;`
`   }`

516bit静态表查找法Precompute_16bit

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;`
`}`

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 ;`
`  }`

http://www.everything2.com/index.pl?node_id=1181258

http://infolab.stanford.edu/~manku/bitcount/bitcount.html

Comments are closed for this entry.