【C语言典例】——day11：统计二进制中1的个数
⭐前言⭐
※※※大家好！我是同学〖森〗，一名计算机爱好者，今天让我们进入刷题模式。若有错误，请多多指教。
⭐往期真集⭐
1、题目描述
链接： 输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
示例1
输入 10 输出 2 说明 十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。
示例2
输入 -1 输出 32 说明 负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1
2、算法分析
方法一：
方法分析
n&1->若A中最后一位为0,0&1 = 0，若最后一位为1,1&1 = 1；然后我们再把A右移一位，再重复判断A中倒数第二位的数字
代码实现
int NumberOf1(int n)
{
int i = 0;
int count = 0;
for (i = 0; i < 32; i++)
{
if ((n >> i) == 0) //若右移后为0跳出循环，不可能再有1了
break;
if (( (n >> i) & 1) == 1) //实现右移和按位与
count++;
}
return count;
}
方法二：
方法分析
还记得我们十进制的数字分离吗？那十进制有数字分离，二进制呢？ 没错，也有。 例1、十进制 123； 我们要想把每个数字分离出来， 123 % 10 = 3； 123 / 10 = 12； …… 这样我们就得到数字 1、2、3. 那二进制呢？ 十进制 15 转换为二进制 00000000 00000000 00000000 00001111； 15 % 2 = 1； 15 / 2 = 7； 而7的二进制 ：00000000 00000000 00000000 00000111； …… 聪明的你是不是恍然大悟呀！
代码实现
int NumberOf1(int n)
{
int i = 0;
int count = 0;
while (n)
{
if (n % 2 == 1)
{
count++;
}
n /= 2;
}
return count;
}
看，没有通过，这是什么原因呢？ 哦！原来我们忘记考虑负数了。 -1 / 2商0余-1 怎么也不可能余1呀！ 那我们就不让他出现负数就好了吗？把它强制类型转换为无符号整型 来！让我们试试。
没错，它可以了
方法三：
方法分析：
n = n & (n-1) 例 n = 13; 1011 13 n 1010 12 n-1 1011 & 1010 = 1010 n = 13 & 12 1010 12 n 1001 11 n-1 1010 & 1001 = 1000 n = 12 & 11 1000 8 n 0111 7 n-1 1000 & 0111 = 0000 n = 8 & 7 0000 0 n 我们可以发现每一次n & (n-1) n就减少一个最右边的1. 我们可以通过循环次数就能找出n中有几个1. 是不是非常高效呢
代码实现：
int NumberOf1(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
3、 程序源码（完整）
#include<stdio.h>
//方法一:
//int NumberOf1(int n)
//{
// int i = 0;
// int count = 0;
// for (i = 0; i < 32; i++)
// {
// if ((n >> i) == 0) //若右移后为0跳出循环，不可能再有1了
// break;
// if (( (n >> i) & 1) == 1) //实现右移和按位与
// count++;
// }
// return count;
//}
//方法二:
//int NumberOf1(int n)
//{
// unsigned int m = (unsigned)n;
// int i = 0;
// int count = 0;
// while (m)
// {
// if (m % 2 == 1)
// {
// count++;
// }
// m /= 2;
// }
// return count;
//}
//方法三:
int NumberOf1(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
int main()
{
int m = 0;
printf("请输入一个整数：");
while(scanf("%d", &m) != EOF)
{
printf("%d的二进制中有%d个1
", m, NumberOf1(m));
printf("请输入一个整数：");
}
return 0;
}