计算数中二进制1的个数

发表于 | | 阅读次数: |

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

简介

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

简单相与法

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

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

核心代码如下:

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

与相邻数相与法

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

1
2
3
0b 1000 & 0b 0111 = 0b 0000
0b 1111 & 0b 1110 = 0b 1110
0b 1010 & 0b 1001 = 0b 1000

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

1
2
3
4
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.

1
2
3
(abc >> 1) & 011 = 0ab = 2a + b (十进制)
(abc >> 2) & 001 = 00a = a (十进制)
abc - ((abc >> 1) & 011) - ((abc >> 2)) & 001 ) = a + b + c

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

1
2
3
4
5
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的个数加起来，

与特定值相与法

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

1
2
3
4
5
  0b 1111 1111  
& 0b 0101 0101  = 0b 0101 0101

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

把上述俩个结果相加得:

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

这只是计算出每两位所含的1，即10（为2）个。同理计算每4位的，再计算每8位的等等…

1
2
3
#define M1 0x55    // 0b 0101 0101</strong>  
#define M2 0x33    // 0b 0011 0011</strong>  
#define M3 0x0F    // 0b 0000 1111</strong>

上述三个宏用来测试八位数中的二进制中1的个数，其测试代码如下：

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

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

1
2
3
4
5
6
7
8
9
10
11
#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)。