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

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

该题我为笨办法,与题解不同,如有疑问和见解,欢迎大家在评论区提出

题目链接:

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

描述

输入一个整数 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;
}

坑:

结果直接超时,只通过了44%的数据,后面发现没有通过的样例是:-2147483648(本以为自己看了数据范围,简单题就难不住自己,谁知有这么一个坑🫥),后面拿-1去测试,发现也不可通过,才想起来算术右移和逻辑右移

讲解:

算术右移:

算术右移就是如果为有符号数,则在左边一直补符号位;

如果为无符号数,则在左边补0

逻辑右移:

逻辑右移就是不管是有符号数还是无符号数都是在左边补0

该题做法:

右移不行,那就左移嘛~

讲到这里就不得不提一下-2147483648这个数据在内存中的存储了!!!!!!!!!

在这里,有些人可能就想:int占4个字节,在内存中占32个比特位,由于最高位为符号位,为1表示负数,为0表示正数,而-2147483648是int类型的最小值,所以-2147483648在内存中的存储为:1111 1111 1111 1111 1111 1111 1111 1111,可该数在计算机中却是十进制的-1(题目中也提示过)

而-2147483648在内存中的存储:

符号位：1（表示负数）
数值位：10000000000000000000000000000000

然后我的想法是:设置一个int flag = 2147483648,把一开始的n>>=1改为n<<=1,if(n&flag)count++;其他的不变,(代码如下)

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

到这里你可能有思路了,但是int类型的最大值是 2147483647,又掉进坑了吧,既然int存不了,那就开long long嘛,所以:long long int flag=2147483648;

所以AC代码就是:

AC代码:

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

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