C语言经典例题|【C语言典例】——day11（统计二进制中1的个数） C语言经典例题|c语言

?前言?

※※※大家好！我是同学〖森〗，一名计算机爱好者，今天让我们进入刷题模式。若有错误，请多多指教。点赞 ? 收藏留言都是我创作的最大的动力！

?往期真集?

DAY:10	day10：杨氏矩阵
DAY:9	day9：倒置字符串
DAY:8	day8：猜名次
DAY:7	day7：尼科彻斯定理
DAY:6	day6：猴子吃桃

目录
?前言?
※※※大家好！我是同学〖森〗，一名计算机爱好者，今天让我们进入刷题模式。若有错误，请多多指教。
?往期真集?
1、题目描述
2、算法分析
方法一：
方法分析
代码实现
方法二：
方法分析
代码实现
方法三：
方法分析：
代码实现：
3、程序源码（完整）
4、运行结果

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;
101113n
101012n-1
1011 & 1010 = 1010n = 13 & 12
101012n
100111n-1
1010 & 1001 = 1000n = 12 & 11
10008n
01117n-1
1000 & 0111 = 0000n = 8 & 7
00000n
我们可以发现每一次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 //方法一://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\n", m, NumberOf1(m)); printf("请输入一个整数："); } return 0; }

4、运行结果