ZT 计算一个无符整数中1Bit的个数(1) 2010-04-20 10:52:48

计算一个无符整数中1Bit的个数(1) 2010-04-20 10:52:48

分类: C/C++

[转]计算一个无符整数中1Bit的个数(1)
 

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。
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 ;

   }

与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 =1001011000111111

+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 =0111111111010011

----------------------------------------------------------------------

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

55 =         00000101         00000101

+ 66 =         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 ;
}
 
上一篇:Dijkstra 算法——计算有权最短路径(边有权值)


下一篇:Floyd-Warshall算法计算有向图的传递闭包