Brains


on Algorithm, 求比特位中1的数目

计算一个数字中 1的个数 的算法

本文主要收集了一些很nice的方法,用来计算一个数,其二进制形式中1的位数。

简介

李明老师的C语言中级课程中,讲解了这一算法,无奈记性不好。。为了以后能时常看到,现记录下来。

简单相与法

比如一个二进制数0b 1111 1111 = 0xFF,只需要:

1、与0b 0000 0001 = 0x01相与,如果为真,则个数加1;
2、与0b 0000 0010 = 0x02相与,如果为真,则个数加1;
....
....
n、如果这个数是16位的,必须相与到0xFFFF才能结束

核心代码如下:


...
...
for( i = 0; i < 16; i++ )
{
  if( num & ( 1 << i ) )    // 左移 i 位 => 1 * 2 ^ i
  {
    count++;
  }
}
...
...

与相邻数相与法

注意这种情况:一个数与这个数减1相与,会把这个数的最后面的一位1变为0.如下情况:


0b 1000 & 0b 0111 = 0b 0000
0b 1111 & 0b 1110 = 0b 1110
0b 1010 & 0b 1001 = 0b 1000

这就引出下面的一种算法,其核心代码如下:


...
...
while( num != 0 )
{
  num = num & num - 1; // 每次把最后一个1变为0
  count++;
}
...
...

每三位计算一次

这一个算法实在CSAPP课上老师讲解的一个算法,现在给它添加上去。原理就是对每3个比特计算一下1的个数,可以同步进行,计算一个32位的数字,最多执行11次。

具体做法:

假设这3为比特位为 abc,那么这3位比特位含1的个数为 a + b + c。而 abc 换成十进制为 4a + 2b + c,注意怎么从 4a + 2b + c 变到 a + b + c,因为后者才是这3位数含有的1的个数。这个是通过下面一个式子实现的。假设一个3比特位的数 abc.
( abc >> 1 ) & 011 = 0ab = 2a + b (十进制)
( abc >> 2 ) & 001 = 00a = a (十进制)

abc - ((abc >> 1) & 011) - ((abc >> 2)) & 001 ) = a + b + c

那么就有如下的代码,可以计算一个32位数中1的个数,如下所示:


1 int bitcount( unsigned int n )
2 {
3     unsigned int tmp;
4  
5     tmp = n - ((n >> 1) & 033333333333 ) - ((n >> 2) & 011111111111 );
6  
7     return (( tmp + (tmp >> 3)) & 030707070707 ) % 63;
8 }

最后那个 return语句是为了把这个数字每3位中的1的个数加起来,

与特定值相与法

上一个算法看似很好,但如果遇到0xFF和0xFFFF之类全1的数,性能就下降了。对此想到一种新的算法.


0b 1111 1111
& 0b 0101 0101 = 0b 0101 0101


0b 0101 0101
& 0b 0101 0101 = 0b 0101 0101

把上述俩个结果相加得:

0b 0101 0101 + 0b 0101 0101 = 0b 1010 1010

这只是计算出每两位所含的1,即10(为2)个。同理计算每4位的,再计算每8位的等等...

#define M1 0x55 // 0b 0101 0101
#define M2 0x33 // 0b 0011 0011
#define M3 0x0F // 0b 0000 1111
上述三个宏用来测试八位数中的二进制中1的个数,其测试代码如下:


num = num & M1 + ( ( num >> 1 ) & M1 );
num = num & M2 + ( ( num >> 2 ) & M2 );
num = num & M3 + ( ( num >> 4 ) & M3 );

最后的num地值,即为1的个数
假设为32位的数,那么需要5个宏定义,分别如下:

#define M1 0x55555555
#define M2 0x33333333
#define M3 0x0F0F0F0F
#define M4 0x00FF00FF
#define M5 0x0000FFFF


num = num & M1 + ( ( num >> 1 ) & M1 );
num = num & M2 + ( ( num >> 2 ) & M2 );
num = num & M3 + ( ( num >> 4 ) & M3 );
num = num & M4 + ( ( num >> 8 ) & M4 );
num = num & M5 + ( ( num >> 16 ) & M5 );

最后的num地值,即为1的个数。这种算法时间复杂度固定,为O(1)

comments powered by Disqus

纸上得来终觉浅,绝知此事要躬行~