JZ15 二进制中1的个数（两种解法）（C语言）

用户11039529

发布于 2024-03-25 15:26:08

1810

文章被收录于专栏：算法学习日常算法学习日常

个人博客主页：https://blog.csdn.net/2301_79293429?type=blog

专栏：https://blog.csdn.net/230

题目链接:

二进制中1的个数_牛客题霸_牛客网 (nowcoder.com)

看本篇文章之前建议先看看该文章(讲了坑点和易错点):

JZ15 二进制中1的个数（牛客）（C语言）-CSDN博客

描述

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围：−2^31<=n<=2^31−1

即范围为:−2147483648<=n<=2147483647

示例1

输入：

返回值：

说明：

十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

示例2

输入：

-1

返回值：

说明：

负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

法一:

//遍历每一个比特位，注意：不可用如下代码遍历

/*下列代码超时的原因，右移的时候反复补符号位，遇见负数会陷入死循环*/
// int NumberOf1(int n)
// {
//     int count=0;
//     while(n)
//     {
//         if(n&1)//如果最后一位为1
//             count++;
//         n>>=1;
//     }
    
//     return count;
// }

/*正确代码*/
int NumberOf1(int n)
{
    int count = 0;
    for(int i=0;i<32;i++)
    {
        if ((n>>i) & 1)//如果该位一位为1
            count++;
        
    }

    return count;
}

法二:

如果不懂请看开头推荐的文章:JZ15 二进制中1的个数（牛客）（C语言）-CSDN博客

int NumberOf1(int n )
{
    long long flag=2147483648;
    int count=0;
    while(n)
    {
        if(n&flag)//如果第一位为1
            count++;
        n<<=1;
    }
     
    return count;
}

错误写法一:

有人发现负数通过不了就先把负数标记一下,再将其转化为正数,再最后把符号位的1加入总数,就有如下代码

  int NumberOf1(int n )
  {
     int flag=0;
     if(n<0)
      {
          flag=1;
          n=-n;
      }
      int count=0;
      while(n)
      {
          if(n&1)//如果最后一位为1
              count++;
          n>>=1;
      }
      if(flag==1)
      count++;
     return count;
 }

但是再想想-2147483648这个数,转化为正数就是2147483648,但是int最大也只能是2147483647,

所以该方法不行,如果这题让n的类型让你自己设定,你就可以设定long long,该方法就可行

错误写法二:

具体原因已经写在该代码开头啦~

/*下列代码超时的原因，右移的时候反复补符号位，遇见负数会陷入死循环*/
// int NumberOf1(int n)
// {
//     int count=0;
//     while(n)
//     {
//         if(n&1)//如果最后一位为1
//             count++;
//         n>>=1;
//     }
    
//     return count;
// }

最后祝大家题题AC,天天只盼着做个WA梦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除

int