1、问题描述
输入一个整数n,输出该数32位二进制表示中的个数。
2、题目分析
本题归根结底是考察 操作符
① 方法一:将目标数n的二进制的最低位与1进行按位与比较,通过循环不断的将最低位进行移位。
②方法二:通过不断的%2和/2,当%2的结果为1的时候,则证明二进制中有1
③方法三:巧妙算法: n=n&(n-1)
3、算法设计
🍑算法一
①:二者进行按位与&比较,若n&1的数值为1,则说明n的二进制里有1。
②:通过for循环,不断将n的最低位向右移,即可遍历整个二进制,也就找出了二进制中的1
③:通过判断(n >> i) & 1的值是否等于1,是则count++
参考代码如下↓
🍑算法二
①:我们对10进行先%2,余下的零就是对应二进制最低位的0。
②:每次将%2后的结果舍去,若10/2=5(二进制为101,即为1010舍去0后的结果)
③:通过不断的%2和/2,当%2的结果为1的时候,则证明二进制中有1,于是count++。
参考代码如下↓
可当我们测试-1的时候,结果却不和预期,我们知道-1看的是在内存的二进制序列里1的个数
所以我们可以把n当成无符号数 来处理即可解决。
我们把传参的n的类型改成unsigned int即可
🍑算法三(最巧妙)
巧妙算法: n=n&(n-1) ,当二进制中有多少个1,则循环多少次,比前面两种方法循环次数少,效率更高。
4、代码实现📝
完整代码📝
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> 方法一: //int Numberof1(int n) //{ // int i = 0; // int count = 0; // for (i = 0; i < 32; i++) // { // if (((n >> i) & 1) == 1) // { // count++; // } // } // return count; //} 方法二: //int Numberof1(unsigned int n) //{ // int count = 0; // while (n) // { // if (n % 2 == 1) // count++; // n /= 2; // } // return count; //} 方法三: int Numberof1(unsigned int n) { int count = 0; while (n) { n = n & (n - 1); count++; } return count; } int main() { int n = 0; printf("请输入一个数:\n"); scanf("%d",&n); int ret = Numberof1(n); printf("二进制中1的个数=%d\n", ret); return 0; }
5、总结
此题目为谷歌的面试题目,前两个算法规规矩矩,但最后一个算法比较难想到,不过没关系,慢慢熟练就好。