C语言每日一练——第2天:二进制中1的个数

简介: C语言每日一练——第2天:二进制中1的个数

1、问题描述


输入一个整数n,输出该数32位二进制表示中的个数。


2、题目分析


本题归根结底是考察 操作符


① 方法一:将目标数n的二进制的最低位与1进行按位与比较,通过循环不断的将最低位进行移位。

②方法二:通过不断的%2和/2,当%2的结果为1的时候,则证明二进制中有1

③方法三:巧妙算法: n=n&(n-1)


3、算法设计


🍑算法一

0a2653c851af460fa595bd959398a8f1.png

①:二者进行按位与&比较,若n&1的数值为1,则说明n的二进制里有1。

②:通过for循环,不断将n的最低位向右移,即可遍历整个二进制,也就找出了二进制中的1

③:通过判断(n >> i) & 1的值是否等于1,是则count++

参考代码如下↓

2d65d23f6d4748949b924e4057485923.png


🍑算法二

6de278e6d6694ce5bb08e7e842b7e74b.png

①:我们对10进行先%2,余下的零就是对应二进制最低位的0。

②:每次将%2后的结果舍去,若10/2=5(二进制为101,即为1010舍去0后的结果)

③:通过不断的%2和/2,当%2的结果为1的时候,则证明二进制中有1,于是count++。

参考代码如下↓

8ec4f2997fb246878c34ecd6d122b7c6.png12c3b7f3f8814309a195c64f051d4445.png


可当我们测试-1的时候,结果却不和预期,我们知道-1看的是在内存的二进制序列里1的个数

所以我们可以把n当成无符号数 来处理即可解决。

我们把传参的n的类型改成unsigned int即可

34e8d716411043c08c7ffba9fbba23de.png

🍑算法三(最巧妙)

92ba0822ed0b46e1ae72df8a17d3a45b.png

巧妙算法: n=n&(n-1) ,当二进制中有多少个1,则循环多少次,比前面两种方法循环次数少,效率更高。

d79b274929334152a6d38be91e2d1be3.png


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、总结


此题目为谷歌的面试题目,前两个算法规规矩矩,但最后一个算法比较难想到,不过没关系,慢慢熟练就好。


相关文章
|
6月前
|
存储 人工智能 安全
C语言:选择+编程(每日一练Day15)
C语言:选择+编程(每日一练Day15)
85 2
|
6月前
|
存储 C语言
C语言实现二进制到十进制
C语言实现二进制到十进制
64 0
|
5月前
|
C语言
C语言---二进制位置0或者置1
C语言---二进制位置0或者置1
|
5月前
|
C语言
【C语言刷题系列】计算整数的二进制位中1的个数 (三种方式)
【C语言刷题系列】计算整数的二进制位中1的个数 (三种方式)
|
5月前
|
C语言
C语言-----计算两个int(32位)整数m和n的二进制表达中,有多少个位(bit)不同?
C语言-----计算两个int(32位)整数m和n的二进制表达中,有多少个位(bit)不同?
|
5月前
|
C语言
C语言----获取一个整数二进制序列中所有的偶数位和奇数位,分别打印出二进制序列
C语言----获取一个整数二进制序列中所有的偶数位和奇数位,分别打印出二进制序列
|
5月前
|
存储 C语言
C语言---求一个整数存储在内存中的二进制中1的个数--3种方法
C语言---求一个整数存储在内存中的二进制中1的个数--3种方法
|
6月前
|
测试技术 C语言
C语言每日一练Day03——移除元素
C语言每日一练Day03——移除元素
|
6月前
|
C语言
C语言每日一练——Day02:求最小公倍数(3种方法)
C语言每日一练——Day02:求最小公倍数(3种方法)
|
6月前
|
C语言
C语言每日一练——Day01:求最大公约数(三种方法)
C语言每日一练——Day01:求最大公约数(三种方法)