计算任意一个整数的二进制数有几个1

大家好啊，今天想分享一下上周工作中遇到的小问题，就是求一个数的二进制数中的1到底有几个的方法。
上周在做一个项目中，我需要求一个变量中的二进制数值到底有几个二进制数为1，可能第一印象，大家都会想到for循环，通过移位遍历这个数的二进制所有位的方法来求解。当时我也想到了这个，但是我又感觉要写一大串的代码，懒得写这么多，然后查了一些，发现了许多种方法，感觉一种还是比较巧妙的，分享一下，我最终采用了这种，但是感觉大部分人都不太熟悉，那天写了，导师给我看了好久。

代码如下

原理：for(;date;date &= (date-1),++bit_number);
一一消去最右边的1，直道这个数被全部消0，统计销零的次数即是这个数的被置位的位数。
解释：n &= (n – 1)能清除最右边的1，很容易理解，就是因为进位产生的，从二进制的角度讲，n相当于在n - 1的最低位加上1。
如 5（0b0101）=4(0b0100)+1(0b0001),
消去最右边的第一个1： 5（0b0101）& 4(0b0100) = 2(0b0100)
消去最右边的第二个1: 2(0b0100) & 1(0b0001) = 0(0b0000)

演示代码如下：

#include"stdio.h"
 void main()
 {
     int date=0,bit_number=0;
     scanf("%d",&date);
     printf("输入的数值为：%d\n",date);
        for(;date;date &= (date-1),++bit_number);
    printf("这个数的二进制为1的位数为：%d\n",bit_number);
 }

运行结果

说明：
使用这种算法，最坏情况下，只有在数字 n 对应的二进制全部都是1的情况下(3, 7, 15, 31, 63....)，会执行二进制位数次循环。而一般情况下，如果只有1个1，那么只需要循环1次，如果有2个1，只需要循环2次。大大提高了运算效率。

还有其他许多方法，大家感兴趣可以去搜索看看，如下放几个，不过多分析了，时间有点晚了，准备睡觉了。

移位普通法（大家都能想到）

说一下，这种方法虽然很容易想到，我们不难发现，如果这个数据类型是无符号整数型，也就是占着32位，那相当于要循环32次才可以找出来。

int BitCount(unsigned int n)
{
    unsigned int c =0 ; // 计数器
    while (n >0)
    {
        if((n &1) ==1) // 当前位是1
            ++c ; // 计数器加1
        n >>=1 ; // 右移
    }
    return c ;
}

动态建表法

int BitCount3(unsigned int n) 
{ 
    // 建表
    unsigned char BitsSetTable256[256] = {0} ; 

    // 初始化表 
    for (int i =0; i <256; i++) 
    { 
        BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2]; 
    } 

    unsigned int c =0 ; 

    // 查表
    unsigned char* p = (unsigned char*) &n ; 

    c = BitsSetTable256[p[0]] + 
        BitsSetTable256[p[1]] + 
        BitsSetTable256[p[2]] + 
        BitsSetTable256[p[3]]; 

    return c ; 
}

填表的原理：

根据奇偶性来分析，对于任意一个正整数n
1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。
2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。

查表的原理

对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。

注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以87654321（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。
10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13

静态表-4bit

int BitCount4(unsigned int n)
{
    unsigned int table[16] = 
    {
        0, 1, 1, 2, 
        1, 2, 2, 3, 
        1, 2, 2, 3, 
        2, 3, 3, 4
    } ;

    unsigned int count =0 ;
    while (n)
    {
        count += table[n &0xf] ;
        n >>=4 ;
    }
    return count ;
}

平行法

先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

int BitCount4(unsigned int n) 
{ 
    n = (n &0x55555555) + ((n >>1) &0x55555555) ; 
    n = (n &0x33333333) + ((n >>2) &0x33333333) ; 
    n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 
    n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; 
    n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 

    return n ; 
}

位标志法

struct _byte 
{ 
    unsigned a:1; 
    unsigned b:1; 
    unsigned c:1; 
    unsigned d:1; 
    unsigned e:1; 
    unsigned f:1; 
    unsigned g:1; 
    unsigned h:1; 
}; 

long get_bit_count( unsigned char b ) 
{
    struct _byte *by = (struct _byte*)&b; 
    return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h); 
}

完美法

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

免责说明：上述内容部分引用博客内容，用于知识的理解，技术交流传播，版权归原作者所有，如有不妥，联系修改
参考资料：
算法-求二进制数中1的个数 - 翰墨小生 - 博客园 (cnblogs.com)

欢迎关注本人微信公众号：那个混子

记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！

单片机类嵌入式交流学习可加企鹅群：120653336