如何计算32位数中‘1’的个数

本文内容来自微信公众号嵌入式Linux。支持原创，尊重原创！

大神计算32位数中‘1’的个数

首先直接看代码：

int count_bits(int x)
{
    register int xx=x;
    xx=xx-((xx>>1)&0x55555555);
    xx=(xx&0x33333333)+((xx>>2)&0x33333333);
    xx=(xx+(xx>>4))&0x0f0f0f0f;
    xx=xx+(xx>>8);
    return (xx+(xx>>16)) & 0xff;
}

我看到后的第一反应就是懵逼，不断的位移不断地按位与，到最后是什么结果不仔细分析我看不出来，看了函数名，也大概猜到了是统计什么位的个数的。

韦大神如何实现相同的功能

同样，先直接上代码：

#include "stdio.h"
#include "time.h"

int count_bits(int x)
{
  register int xx=x;
  xx=xx-((xx>>1)&0x55555555);
  xx=(xx&0x33333333)+((xx>>2)&0x33333333);
  xx=(xx+(xx>>4))&0x0f0f0f0f;
  xx=xx+(xx>>8);
  return (xx+(xx>>16)) & 0xff;
}

int count_bits2(int x)
{
    int i = 0;
    int s = 0;
    for(i = 0;i<32;i++)
    {
        if(x&0x01)
            s ++;
        x = x>>1;
    }
    return (s);
}

int main(void)
{
    printf("%d\n",count_bits(12345678));
    printf("%d\n",count_bits2(12345678));
}

OK，只看count_bits2函数，就简单太多了！

刨析大神代码

先来个简单的例子：

#include "stdio.h"

int count_bits4(char x)
{
    x = (x&0x55) + ((x>>1)&0x55);
    x = (x&0x33) + ((x>>2)&0x33);
    x = (x&0x0F) + ((x>>4)&0x0F);
    return x;
}

int main()
{
    printf("%x\n",count_bits4(0x12));
}

贴上运行结果：

我们现看看下面这段 0x55 = 0b01010101 0x33 = 0b00110011 0x0F = 0b00001111

图中表示相邻两个数不断相加，知道这个数据的长度
比如：

如果要计算0x34里面1的个数，那么先将其转换成二进制，然后把相邻的二进制位相加，再然后把相邻的两位数相加，最后把相邻的四位数相加。

复杂一点的

上代码：

#include "stdio.h"

int count_bits3(long long s)
{
    s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
    s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
    s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
    s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
    s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
    s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);
    return (int)s;
}
int main()
{
    printf("%x\n",count_bits3(0x122312351345134));
}

运行结果输出15。这里就不再贴图了。感兴趣的可以自己测试一下。
搞清楚了上面的那段代码，再看下面这段代码，就会好很多了。

实测大神的代码是如何吊打普通代码的

上菜：test1.c

#include "stdio.h"
#include <time.h>
int count_bits(int x)
{
  register int xx=x;
  xx=xx-((xx>>1)&0x55555555);
  xx=(xx&0x33333333)+((xx>>2)&0x33333333);
  xx=(xx+(xx>>4))&0x0f0f0f0f;
  xx=xx+(xx>>8);
  return (xx+(xx>>16)) & 0xff;
}
int main(void)
{
    clock_t start, end;
    start = clock();
    unsigned int i = 0;
    for(i = 0;i<10000000;i++){
        count_bits(12345678);
    }
    printf("%d\n",count_bits(12345678));
    end = clock();
    double seconds  =(double)(end - start)/CLOCKS_PER_SEC;
    fprintf(stderr, "Use time is: %.8f s\n", seconds);
    return (0);
}

test2.c

#include "stdio.h"
#include <time.h>
int count_bits2(int x)
{
    int i = 0;
    int s = 0;
    for(i = 0;i<32;i++)
    {
        if(x&0x01)
            s ++;
        x = x>>1;
    }
    return (s);
}
int main(void)
{
    clock_t start, end;
    start = clock();
    unsigned int i = 0;
    for(i = 0;i<10000000;i++){
        count_bits2(12345678);
    }
    printf("%d\n",count_bits2(12345678));
    end = clock();
    double seconds  =(double)(end - start)/CLOCKS_PER_SEC;
    fprintf(stderr, "Use time is: %.8f s\n", seconds);
    return (0);
}

运行结果：

个人感受

从代码的可读性和维护上来说，我喜欢韦大神的写法，但是文章开头大神的代码从效率上来说比韦大神的好。各有优略，建议大家再使用的时候权衡利弊！

网友们的做法

u8 cnt；
while(value)
{
    value &= value - 1;
    cnt++;
}
return cnt;

public int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count += 1;
    }
    return count;}

至此，所有！

在此，再次说明，本文原创不是本人，有兴趣的话大家可以关注一下微信公众号“嵌入式Linux”！