大家好啊，今天想分享一下上周工作中遇到的小问题，就是求一个数的二进制数中的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
网友评论