首页 > 试题广场 >

二进制中1的个数

[编程题]二进制中1的个数
  • 热度指数：867196 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个整数 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
算法知识视频讲解
查看答案及解析
添加回答
推荐
writezen头像 writezen 
public class Solution {
    //从n的2进制形式的最右边开始判断是不是1
    /*
    * 该解法如果输入时负数会陷入死循环，
    * 因为负数右移时，在最高位补得是1
    * 二本题最终目的是求1的个数，那么会有无数个
    * 1了。
    */
    //-------------可能陷入死循环的解法---------------------
    public static int NumberOf1_CanNotUse(int n) {
        int count = 0;
        while (n != 0) {
            /*
            * 用1和n进行位与运算，
            * 结果要是为1则n的2进制形式
            * 最右边那位肯定是1，否则为0
            */
            if ((n & 1) == 1) {
                count++;
            }
            //把n的2进制形式往右推一位
            n = n >> 1;
        }
        return count;
    }
    //---------------正解--------------------------------
    //思想：用1（1自身左移运算，其实后来就不是1了）和n的每位进行位与，来判断1的个数
    private static int NumberOf1_low(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }
    //--------------------最优解----------------------------
    public static int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            ++count;
            n = (n - 1) & n;
        }
        return count;
    }
    public static void main(String[] args) {
        //使用n=10,二进制形式为1010，则1的个数为2；
        int n = -10;
        System.out.println(n + "的二进制中1的个数：" + NumberOf1(n));
    }
}

编辑于 2015-08-18 23:23:00 回复(148)
C
鲸鱼lord头像 鲸鱼lord 
//用位运算符可以实现，时间复杂度是O(n),空间复杂度O(1)
int NumberOf1(int n ) {
    // write code here
    int count=0;
    while(n)
    {
        count++;
        n=n&(n-1);
    }
    return count;
}

发表于 2025-03-06 21:59:31 回复(0)
C
牛客804965101号头像 牛客804965101号
#include<stdio.h>
fun(int n)
{
    int i=0,j=0;
    for(i=0;i<32;i++)
    {
        if(n==(n|1<<i)) j++;
     }
    return j;
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d",fun(n));
    return 0;
 }
//为什么我的不行，我在dev里可以运行的呀，第一次来牛客
发表于 2024-10-09 18:18:11 回复(0)
C
StellarVibes头像 StellarVibes
int NumberOf1(int n ) {
    // write code here
    int a = 1;
    int count = 0;
    for(int i = 0;i<32;i++)
    {
        if(n & (a<<i))
        {
            count++;
        }
    }
    return count;
}
发表于 2024-08-15 23:26:40 回复(2)
C
牛客693598049号头像 牛客693598049号

int NumberOf1(int n ) {
    // write code here
    int count = 0;
    while (n)
    {
        count++;
        n = n& (n-1);
    }
    return count;
}
发表于 2024-04-24 13:06:50 回复(0)
C
牛客226699796号头像 牛客226699796号
int NumberOf1(int n )
{
    // write code here
    int count=0;
    for(int i=0;i<32;i++)
    {
        if((n&1)==1)
        {
            count++;
        }
        n=n>>1;
    }
    return count;
}
发表于 2024-02-22 15:49:25 回复(0)
C
陆三九头像 陆三九 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
int NumberOf1(int n ) {
    // write code here
    int count = 0;//计数1
    while(n){
    count++;
    n = n & (n - 1);
    }
    return count;
}


编辑于 2024-01-01 15:50:27 回复(0)
C
李顺利plus头像 李顺利plus 
int NumberOf1(int n ) {
    // write code here
    int sum=0,m;     //sum用于记录1的个数，m用于记录正数情况下取余的结果
    if(n>0){           //正数比较简单，直接转换二进制数个数即可
        while(1){
            m=n%2;
            if(m==1) sum++;
            n=n/2;
            if(n==0) break;
        }
        return sum;
    }
    if(n<0){                      //原始方法求补码
        n=-1*n;                   //先变成正数
        int a[32];                    
        for(int i=31;i>=0;i--){          //用a数组记录n的正数的二进制数
            a[i]=n%2;
            n=n/2;
        }
        a[0]=1;                         //符号位取反
        for(int i=1;i<=31;i++){          //除符号位外各位0变1，1变0
            if(a[i]==0){
                a[i]=1;
                continue;
            }
            else{
                a[i]=0;
                continue;
            }
        }
        a[31]=a[31]+1;                 //整体+1
        for(int i=31;i>0;i--){              //考虑+1后的进位问题
            if(a[i]==2) a[i-1]=a[i-1]+1;
        }
        if(a[0]==2) a[0]=1;    //高位产生溢出时，符号位为1不变，应对-2147483648
        for(int i=0;i<32;i++){      //求1的个数
            if(a[i]==1) sum++;
        }
        return sum;
    }
    return 0;
}

发表于 2022-10-07 18:02:56 回复(0)
C
我叫马牛逼头像 我叫马牛逼 
int NumberOf1(int a ) {
    // write code here
    

int count = 0;
    if (a >= 0)
    {
        while (a)
        {
            if (a & 1) {//可以判断出当前a最后一位是1还是0
                count++;
            }
            a = a >> 1;
        }
    }
    else
    {
        //负数右移，我这个编译器是算术右移（大多数编译器都是算术右移）
        //算术右移就是，最右边数丢弃，左边补符号位，因为是负数也就是补1
        //这里如果还用while(a)就会一直死循环下去，因为左边会一直补1
        //但我们是知道整形是32位存储在内存里面的，我们循环32次即可
        for (int i = 0;i < 32;i++)
        {
            if (a & 1) {//可以判断出当前a最后一位是1还是0
                count++;
            }
            a = a >> 1;
        }
    }
    return count;
}

发表于 2022-07-27 19:42:44 回复(0)
C
我爱无双2018头像 我爱无双2018
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int NumberOf1(int n ) {
    // write code here
    int sum = 0;
    for(int i = 0;i<32;i++){
        if(n == (n|1<<i)){
            sum++;
        }
    }
    return sum;
}
发表于 2022-05-21 21:51:46 回复(0)
C
ouyangshiqi头像 ouyangshiqi 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int NumberOf1(int n ) {
    // write code here
//     int i = 0;
//     int count = 0;
    
//     while (i < 32)
//     {
//         if (n & 1<<i)
//         {
//             count++;
//         }
//         i++;
//     }
    
//     return count;
    
    int count = 0;
    
    while (n != 0)
    {
        n = n & (n-1);
        count++;
    }
    
    return count;
}

发表于 2022-03-23 09:50:46 回复(0)
C
CreatorSY头像 CreatorSY 
int NumberOf1(int n ) {
    int ret = 0;

    for (int i = 0; i < 32; i++, n >>= 1)
        ret += n & 0x1;

    return ret;
}
发表于 2022-01-07 22:43:24 回复(0)
提交观点

问题信息

基础数学
来自：“一战通offer”互...
难度：
11条回答 239572浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二进制中1的个数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号