题目介绍
写一个函数返回参数二进制中 1 的个数。
牛客网也有这道题，OJ链接
需要用到的知识点：按位与操作符&的原理及使用，右移操作符>>的原理及使用，二进制的转换
解法一（有bug）
我们需要将得到的整数转化为二进制，那么有如下代码：
#include <stdio.h>
int count_bit(int n)
{
int count = 0;
//将得到的数转化为二进制
while (n)
{
//只要二进制位中有1则计数器加1
if (n % 2 == 1)
{
count++;
}
n /= 2;
}
return count;
}
int main()
{
int num = 0;
printf("请输入一个想要计算的整数:\n");
scanf("%d", &num);
printf("该整数二进制中1的个数为%d", count_bit(num));
return 0;
}
程序运行结果：
这里我们就发现了一个bug，这个算法对于负数并不是很友好，原因如下：
负数在内存中是以补码的形式存储的，本算法只适合正整数。
解法二（效率较慢）
比如我们现在需要计算10在二进制中1的个数。
首先我们第一步就是将它在内存中以32位二进制表示出来：
0000 0000 0000 0000 0000 0000 0000 1010
第二步就是想办法统计二进制中1的个数，那么如何统计呢？这里我们就需要用到位运算了。
介绍一下&按位与操作符，它的作用就是比较两个数字的二进制位，全部为1则结果为1，否则结果为0。
所以我们这里就可以将10和1进行按位与操作&，如果结果为1，就让计数器加一，并且每比较一次，将10>>1
原理如下：
1的二进制表示为0000 0000 0000 0000 0000 0000 0000 0001，所以我们每一次比较的时候有效位就是右边第一位，每次比较完后，我们将10的二进制位右移一格，即可更新比较的位置，这样循环32次即可将10的每一位都和1进行比较，达到题目的要求。
图解：
代码
#include <stdio.h>
int count_bit(int num)
{
//计数器
int count = 0;
for (int i = 0; i < 32; i++)
{
//按位与的结果为1则计数器加1
if (num & 1 == 1)
{
count++;
}
//每次比较完后，将待比较的数右移一位
num = num >> 1;
}
return count;
}
int main()
{
int num = 0;
printf("请输入一个想要计算的整数:\n");
scanf("%d", &num);
printf("该整数二进制中1的个数为%d", count_bit(num));
return 0;
}
程序运行结果：
本解法的效率其实是比较低的，因为需要循环32次。
解法三（优解）
我们先了解一下这个表达式n=n&(n-1);这个表达式的效果是将当前n的二进制中最右边的1给移除。
我们以10为例，图解如下：
所以我们有了一下算法：只要n!=0，就让n=n&(n-1)，并且计数器加1。
代码如下：
#include <stdio.h>
int count_bit(int num)
{
//计数器
int count = 0;
while (num)
{
num = num & (num - 1);
count++;
}
return count;
}
int main()
{
int num = 0;
printf("请输入一个想要计算的整数:\n");
scanf("%d", &num);
printf("该整数二进制中1的个数为%d", count_bit(num));
return 0;
}
程序运行结果：
总结
提供了三种解法，其中第一种不推荐，因为有一定的漏洞，第二种解法最容易理解，但是效率偏低，第三种解法是比较推荐的，并且这个算法也很巧妙。