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

简介

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

简单相与法

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

核心代码如下:

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的个数,如下所示:

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

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

与特定值相与法

上一个算法看似很好,但如果遇到 0xFF0xFFFF 之类全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</strong>  
#define M2 0x33    // 0b 0011 0011</strong>  
#define M3 0x0F    // 0b 0000 1111</strong>  

上述三个宏用来测试八位数中的二进制中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)


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