Chinaunix首页 | 论坛 | 博客
  • 博客访问: 526849
  • 博文数量: 96
  • 博客积分: 2960
  • 博客等级: 少校
  • 技术积分: 1850
  • 用 户 组: 普通用户
  • 注册时间: 2006-12-11 15:25
文章分类

全部博文(96)

文章存档

2009年(37)

2008年(59)

我的朋友

分类:

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改进。

 

2Bit1稀疏Sparse Ones

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

理解这个算法的核心,只需理解2个操作:

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

这个算法循环的次数是bit位为一的个数。也就说有几个Bit1,循环几次。对Bit1比较稀疏的数来说,性能很好。如: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的个数。

 

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

使用静态数组表,列出所有8bit(256)无符号数含有Bit1的个数。将32Bit n4部分,直接在表中找到对应的Bit1的个数,然后求和。

这是最快的方法了。缺点是需要比较大的内存。

  

516bit静态表查找法Precompute_16bit

因为在计算64int时,以上方法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个计数器,每个计数器的值就是这2Bit1的个数;继续合并相邻的2个“计数器“,使i成为8个计数器,每个计数器的值就是4Bit1的个数。。依次类推,直到将i变成一个计数器,那么它的值就是32Biti中值为1Bit的个数。

举个例子,假设输入的i值为10010111011111010101101110101111(十进制2541575087

计算过程如下:(共221

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

计算过程如下:(共221

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,4Counter8bit计数器的和(不进行合并计数器的操作)。

        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)的和,并根据掩码求出世纪的有效数字。其实将45步的与掩码运算合并为只进行一次。

     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。认为tmp8进制描述的。8进制的每个数字都是n中相应的每3Bit位所描述的数字。最后返回这些8进制数的和就是我们需要的最终答案了。关键是,将相邻的8进制对加在一起,然后计算时记得对63(2(3+3)次幂)-1)进行除运算取得余数。实现方法是:使用tmp右移3位、然后与自身相加,再与一个适当的掩码进行AND操作,产生一个数,这个数是相邻6位中含有Bit1的个数。

64位数来说,应该比8进制数的多3倍(4倍),所以要对102364*24次幂)-1)求模。(这算法在X11代码中被用到过。)

 

参考:

 

阅读(1423) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~