计算二进制数据中1的个数

在工作中经常遇到如下问题：任意给定一个32位无符号整数n，求value的二进制表示中1的个数，比如value = 0x05（0b0101）时，返回2，value =  0x8e（0b1000 1110）时，返回4。下面给出几种常用的解法，在文章的最后给出这几种方法的对比结果。

方法一：基础法

基础法最容易理解，直接遍历每一位，代码如下，两种方法的思路是一样的，只是第一种方法必须循环32次，而第二种方法可能会提前结束循环，效率比第一种稍高。最后的测试，是以for循环的这种方法计算的。

uint8_t count_bits_1(uint32_t value)
{
    uint8_t count = 0,i = 0;
    
    for(i = 0; i < 32 ; i++)
    {
        if(value & 0x01)
        {
            count ++;
        }
        value >>= 1;
    }
    return count;
}

uint8_t count_bits_1(uint32_t value)
{
    uint8_t count = 0,i = 0;
    
    while(value)
    {
        if(value & 0x01)
        {
            count ++;
        }   
        value >>= 1;    
    }
    return count;
}

方法二：快速法

这种方法速度比较快，只与value中1的个数有关。如果value的二进制表示中有n个1，那么这个方法只需要循环n次即可。其原理是不断清除value的二进制表示中最右边的1，同时累加计数器，直至value为0，代码如下。

例如当value = 0x0A(0b1010)时，第一次进入while循环后，value = 0b1010 & 0b1001 = 0xb1000，count = 1；第二次进入while循环后，value = 0b1000 & 0b0111 = 0，count = 2；至此value已经为0，函数返回2。

uint8_t count_bits_2(uint32_t value)
{
    uint8_t count = 0;
 
    while(value)
    {
        value &= value - 1;
        count ++;
    }
    return count;
}

方法三：查表法

查表法原理比较简单，直接根据value的值来查询该数据有bit位是置1的，其思想就是空间换时间。表可以是4bit的，也可以是8bit、16bit、32bit的，4bit相对32bit来说，更省空间，但需要计算的时间相对就长了，这里主要是时间和空间的权衡，例如value是uint32_t类型时，用4bit表来查需要查询8次，而用32bit表来查询只需要1次。8bit表查询法是一个较中庸的方法。

注意：如果表使用const修饰，则查询时会读FLASH，不定义为const时，表会被拷贝到RAM中，查询时会读RAM。读RAM的速度要快于读FLASH。

static uint8_t table[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, 
}; 

uint8_t count_bits_3(uint32_t value)
{
    uint8_t count = 0;

    count  =  table[value & 0xff] +
              table[(value  >>8) & 0xff] +
              table[(value  >>16) & 0xff] +
              table[(value  >>24) & 0xff] ;
    return count ;
}

方法四：高级法（平行法）

uint8_t count_bits_4(uint32_t value)
{
    value = ( value & 0x55555555 ) + ( (value >>1)  & 0x55555555 ) ; 
    value = ( value & 0x33333333 ) + ( (value >>2)  & 0x33333333 ) ; 
    value = ( value & 0x0f0f0f0f ) + ( (value >>4)  & 0x0f0f0f0f ) ; 
    value = ( value & 0x00ff00ff ) + ( (value >>8)  & 0x00ff00ff ) ; 
    value = ( value & 0x0000ffff ) + ( (value >>16) & 0x0000ffff ) ; 

    return value  ; 
}

这种方法很粗暴，咋一眼不容易看懂，实际上就是将value中的所有bit相加。每次都是将相邻的1组bit位相加，第一次累加相邻的2个bit位，第二次累加相邻的4个bit位，第三次累加相邻的8个bit位，以此类推。

为了方便讲解，我们可以先将题目简单化，假设value是个uint2_t类型的数据(uint2_t类型实际不存在，是假想的，只有2位)，那么求value中有多少个置1的bit位就可以直接用下面的一行代码搞定。这应该一看就能懂了吧？就是将bit1取出来和bit0相加，相加的和就是置1的个数。

/* value为uint2_t类型时 */
value = ( value & 0x01 ) +( (value >> 1) & 0x01 );

/* 或者这样,反正0x05中只有最后2个bit位参与计算 */
value = ( value & 0x05 ) +( (value >> 1) & 0x05 );

好了，再稍微复杂点，假设value是个uint4_t类型的数据，那么代码就可以这样写：

/* value为uint4_t类型时 */
value = ( value & 0x05 ) +( (value >> 1) & 0x05 );
value = ( value & 0x03 ) +( (value >> 2) & 0x03 );

最后再以value为uint8_t类型时举例。

/* value为uint8_t类型时 */
value = ( value & 0x55 ) + ( (value >> 1)  & 0x55 ) ; 
value = ( value & 0x33 ) + ( (value >> 2)  & 0x33 ) ; 
value = ( value & 0x0f ) + ( (value >> 4)  & 0x0f ) ; 

例如当value为0x6D（0b01101101）时，结果为0+1+1+0+1+0+1+1 = 5。下图是计算流程：先把它们相邻的二进制位先相加起来，然后把相邻的两位的数加起来，最后把相邻的四位数加起来。将0x6D带入计算时，第一步得到0b01011001，第二步得到0b00100011，第三部得到0b00000101，即5。搞清楚2、4、8bit的情况后，32bit的情况就是一样的套路。另外，可以注意到在求uint2_t类型时，需要计算1次；计算uint4_t类型时，需要计算2次；计算uint8_t类型时，需要计算3次。那么我们就可以猜测计算uint32_t类型时需要计算5次，计算uint64_t类型时需要计算6次，即。

 方法五：八进制法

uint8_t count_bits_5(uint32_t value)
{
    uint32_t temp= value - ((value >>1) & 033333333333) - ((value >>2) & 011111111111);
    return ((temp+ (temp>>3)) &030707070707) % 63;
}

先说明一点，以0开头的是8进制数，以0x开头的是十六进制数，上面代码中使用了三个8进制数。将value的二进制表示写出来，然后每3bit分成一组，求出每一组中1的个数，再表示成二进制的形式。比如value = 50，其二进制表示为110010，分组后是110和010，这两组中1的个数本别是2和3。2对应010，3对应011，所以第一行代码结束后，tmp = 010011，具体是怎么实现的呢？由于每组3bit，所以这3bit对应的十进制数都能表示为2^2 * a + 2^1 * b + c的形式，也就是4a + 2b + c的形式，这里a,b,c的值为0或1，如果为0表示对应的二进制位上是0，如果为1表示对应的二进制位上是1，所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子，十进制数6（0110）= 4 * 1 + 2 * 1 + 0，这里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二进制表示中有两个1。现在的问题是，如何得到a + b + c呢？注意位运算中，右移一位相当于除2，就利用这个性质！

4a + 2b + c 右移一位等于2a + b，4a + 2b + c 右移量位等于a，然后做减法，4a + 2b + c –(2a + b) – a = a + b + c，这就是第一行代码所作的事。

第二行代码的作用：在第一行的基础上，将tmp中相邻的两组中1的个数累加，由于累加到过程中有些组被重复加了一次，所以要舍弃这些多加的部分，这就是&030707070707的作用，又由于最终结果可能大于63。

需要注意的是，经过第一行代码后，从右侧起，每相邻的3bit只有四种可能，即000, 001, 010, 011，为啥呢？因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题，因为3 + 3 = 6，不足8，不会产生进位。

测试

将以上5种方法放在单片机上运行，比对运行效率。单片机为潘多拉STM32L475，主频80MHz，测试方法如下。

#define TEST_NUMBER    0xFFFFFFFF

start_tick = HAL_GetTick();
for(i = 0; i < 100000; i++)
{
    count = count_bits_1(TEST_NUMBER); 
}
end_tick = HAL_GetTick();
printf("Function 1 result:%d,takes %d ms.\r\n",count,end_tick - start_tick);

对5种算法都采用以上方法进行测试，每种算法执行10万次后计算执行所需时间，最终结果如下。

测试结果（-O0优化）

	方法1	方法2	方法3	方法4	方法5
0x00000000	465ms	22ms	59ms	42ms	45ms
0x00000001	465ms	31ms	59ms	43ms	46ms
0x0000000F	465ms	57ms	59ms	42ms	46ms
0x0000001F	465ms	66ms	59ms	43ms	46ms
0x11111111	465ms	92ms	59ms	42ms	55ms
0x33333333	465ms	162ms	59ms	43ms	55ms
0x77777777	465ms	232ms	59ms	43ms	56ms
0xFFFFFFFF	465ms	302ms	59ms	43ms	56ms

测试结果（-O2优化，仅做参考）

	方法1	方法2	方法3	方法4	方法5
0x00000000	375ms	20ms	33ms	35ms	31ms
0x00000001	376ms	29ms	33ms	35ms	32ms
0x0000000F	380ms	55ms	33ms	35ms	32ms
0x0000001F	381ms	64ms	33ms	35ms	32ms
0x11111111	385ms	90ms	33ms	35ms	41ms
0x33333333	395ms	160ms	32ms	35ms	41ms
0x77777777	405ms	230ms	32ms	35ms	43ms
0xFFFFFFFF	415ms	300ms	32ms	35ms	43ms

结论(不考虑编译器优化)

方法1的效率最低，执行时长固定。

方法2的执行时长受计算值影响，计算值的二进制中，含1越多，执行时间越长。

方法3由于是查表法，执行时间固定。

方法4效率最高，执行时间固定。当bit位个数小于等于4个时，方法2效率高，超过4个时，方法4明显优于方法2。

方法5效率第二，执行时间相对固定，其效率低应该是算法中有取余运算引起的。

综上，在算法选择上优先选择方法4。但这也不是绝对的，适合自己项目才是最好的。例如我的项目中有个触摸按键模块，用bit位来表示当前有多少个键被按下，一般只有1个按键被按下，那么方法2反而是效率最高的。