首页 > 试题广场 >

二进制中1的个数

[编程题]二进制中1的个数
  • 热度指数：861479 时间限制：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)
菩提旭光头像 菩提旭光
绝对最佳答案及分析：
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}
答案正确:恭喜！您提交的程序通过了所有的测试用例
分析一下代码： 这段小小的代码，很是巧妙。
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
编辑于 2015-08-24 16:29:55 回复(196)
luochangan头像 luochangan 
/**
 * 思路：将n与n-1想与会把n的最右边的1去掉，比如
 * 1100&1011 = 1000
 * 再让count++即可计算出有多少个1
 * @author skyace
 *
 */
public class CountOne {
	 public static int NumberOf1(int n) {
			int count = 0;
	        while(n!=0){
	            count++;
	            n = n&(n-1);
	        }
	        
	        return count;
	    }
}

编辑于 2015-08-24 21:40:04 回复(2)
Python
log233头像 log233
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        if n == 0:
            return 0

        ct = 0
        if n < 0:
            n += 2**32  
        while n > 0:
            if n & 1 == 1:
                ct += 1
            n >>= 1
        return ct
发表于 2019-10-27 16:44:08 回复(0)
刘诗歌头像 刘诗歌
给个大众的C++解法吧，C++竟然不在榜上，这怎么行。 
class Solution {
public:
     int  NumberOf1(int n) {
         if(n == 0)
             return 0;
         int count = 0;
         if(n > 0)
         {
             while(n)
             {
                 int tag = n&0x1;
                 if(tag)count++;
                 n=n>>1;
             }
             return count;
         }
         else
         {
             n*=(-1);
             n^=0x7fffffff;
             n+=1;
             while(n)
             {
                 int tag = n&0x1;
                 if(tag)count++;
                 n=n>>1;
             }
             return count+1;
         }
     }
};


发表于 2019-10-06 19:33:51 回复(0)
Python
刀轻城_algo头像 刀轻城_algo 
***********方法0*************
    # 由于负数的存储为补码，但是二进制函数bin()对负数的表达则是用负数的原码，所以负数会出错
    # 所以对于负数，先用～得到各位相反的正数，然后用bin函数表示正数（由于正数bin的表示结果会是正常的），最后由于各位相反，所以正数中的1会是负数中的0，所以减去。
    # 总数是32位这个信息来源于错误案例，应该也可以通过c语言中int为32位推出吧
    def NumberOf1(self, n):
        # write code here
        if n >= 0:
            return bin(n).count('1')
        else:
            return 32 - bin(~n).count('1')



***********方法1*************
    def NumberOf1(self, n):
        # write code here
        count = 0
        for _ in range(32):
            count += n & 1
            n = n >> 1
        return count
编辑于 2019-06-02 09:25:05 回复(0)
Howie59头像 Howie59 
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        for(int i = 0; i < 32;i++){
            if(((n >> i) & 1) == 1){
                ++count;
            }
        }
        return count;
    }
}

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            count++;
            n = n & ( n - 1);
        }
        return count;
    }
}

发表于 2018-08-05 10:25:46 回复(0)
JavaScript
Zfirsty头像 Zfirsty 
//Javascript 描述
function NumberOf1(n)
{
    var num=0;
    while(n){
        num++;
        n=(n-1)&n;
    }
    return num;
}

发表于 2017-07-28 11:27:16 回复(0)
Java
唐宋元明清Z头像 唐宋元明清Z
本题使用无符号位移>>>即可不用考虑整形的正负，还有一种思路是n&(n-1)直接消除最右边的1，大神还是多。。
public class Solution {
    public int NumberOf1(int n) {
        int count=0;
            while(n!=0)
            {
                if((n&1)==1)
                {count++;}
                n=n>>>1;
            }
        return count;
    }
}


public class Solution {
public static int NumberOf1(int n) {
int count = 0;
while(n!=0){
count++;
n = n&(n-1);
}
return count;
}
}

编辑于 2017-07-18 13:31:12 回复(0)
Java
牛油1111头像 牛油1111 
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

发表于 2018-08-23 16:47:57 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
     int  NumberOf1(int n) {
         // 时间复杂度O(N)，空间复杂度O(1)
         int res = 0;
         while (n) {
             ++res;
             n = (n - 1) & n;
         }
         return res;
     }
};

发表于 2022-08-14 13:12:33 回复(0)
99岁熬夜造bug头像 99岁熬夜造bug
#include<stdio.h>
int main()
{
    int a = 0;
    int count = 0;
    int b = 0;
    scanf("%d", &b);
    for (a = 0; a < 32; a++)
    {
        if ((b>>a) & 1 )
        {
            count++;
        }
        
    }
    printf("%d", count);
    return 0;
}
发表于 2022-07-29 19:46:36 回复(0)
Java
陈明燊头像 陈明燊

无符号右移就好了

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while (n!=0){
            if((n&1)==1)count++;
            n >>>= 1;
        }
        return count;
    }
}
发表于 2021-11-14 15:14:11 回复(0)
Python
wengJJ头像 wengJJ
Python
Python的负数显示方式是比较怪的：bin(-3) = -0b11，但实际上存储还是补码
题目要求为32位二进制，所以我们需要使用一个满1的32位数进行一个截断（Python是无限位显示）
（2^32=4294967296=0b11111111111111111111111111111111=0xffffffff）
来进行按位与操作，来获得负数的补码形式 
class Solution:
    def NumberOf1(self, n):
        # write code here
        if n<0:
            n=n&0xffffffff         count=0
        for i in range(32):
#             解法1
#             if n&(1<<i) == 1<<i:
#                 count += 1
#             解法2
            if n != 0 :
                n = (n-1)&n
                count += 1
        return count
发表于 2021-06-12 04:12:42 回复(0)
C/C++
Yeira头像 Yeira 

//整数先与flag，1求与，因为1除了最右边以为之外所有为都是0，再把flag向左移动

class Solution {
public:
     int  NumberOf1(int n) {
         int flag=1;
         int ans=0;
         while(flag)
         {
             if(n&flag)
             {
                 ans++;
             }
             flag=flag<<1;
         }
         return ans;
     }
};


编辑于 2021-05-18 11:19:32 回复(0)
小写H头像 小写H
public class Solution {
    public int NumberOf1(int n) {
    int count = 0;
    for(int i=0;i<32;i++){
        if(((n>>i)&1)==1){
          count++;   
        }
    }
     System.out.println(count);
      return  count;
    }
  }
发表于 2021-05-09 21:31:07 回复(0)
Java
波波突然头像 波波突然 
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        //正数时如果二进制最小位有1，则必定为奇数，此时计1然后右移一位即可
        if(n >= 0){
            while(n>0){
                if((n%2)==1){
                    n>>=1;
                    count++;
                }else{
                    n>>=1;
                }
            }
        }else{//负数时先使用无符号右移，将其变为正数，但是要记得此时如果最低位是1则要先加1
            if(n%2 == -1){
                count++;
            }
            n>>>=1;
            //变成正数后照抄正数代码即可
            while(n>0){
                if((n%2)==1){
                    n>>=1;
                    count++;
                }else{
                    n>>=1;
                }
        }
    }
        return count;
    }
}
//采用位运算符，且相当于直接寻找1的个数，因此无论从时间还是空间复杂度都应该相对较小

发表于 2021-04-27 14:47:04 回复(0)
C/C++
HankingTsou头像 HankingTsou

使用标准库bitset

题干已经表明输出32位二进制中的1的个数，则可以创建一个长度32的bitset，使用count()方法直接计算1的个数：

class Solution {
public:
     int  NumberOf1(int n) {
         bitset<32> bits(n);

         return bits.count();
     }
};
发表于 2021-04-05 08:29:49 回复(0)
cxcxrs头像 cxcxrs 
# -*- coding:utf-8 -*-
"""
评论区一翻，发现都是大佬。
全网python解法中，我的估计是最low的了(￣ェ￣;)
@author cxcxrs
"""
class Solution:
    def NumberOf1(self, n):
        # write code here
        if n == 0:
            return 0
        elif n > 0:  # 正数转化为二进制(不用bin方法)
            res = ""
            while n > 0:
                if n % 2 == 1:
                    res += "1"
                else:
                    res += "0"
                n = n // 2
            return res.count("1")
        else:
            zhen = list(bin(n)[3:])  # 负数转化为二进制（用了bin方法)
            zhen = ['0' for i in range(32 - len(zhen))] + zhen  # 二进制数前面补零，凑满32位
            for i in range(len(zhen)):  # 取反
                if zhen[i] == '1':
                    zhen[i] = '0'
                else:
                    zhen[i] = '1'
            for i in range(len(zhen) - 1, -1, -1):  # 加一
                if zhen[i] == '0':
                    zhen[i] = '1'
                    break
                else:
                    zhen[i] = '0'
            return zhen.count('1')

发表于 2021-03-20 16:04:37 回复(0)
rayhao头像 rayhao
正数：%2为1则有1；/2 。
负数：转化为整数再%2,考虑奇偶补码增减不同 。
特殊考虑溢出情况。

本题要重做看解法（待续）
class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         int temp = n;
         if(n==0) return 0;
         if(n==-2147483648) return 1;
         if(n<0) n=-n;
         while(n>0){
             if(n%2)
                 ++count;
             n >>= 1;
         }
         if(temp<0&&((-temp)%2))
             count = 33 - count;
         else if(temp<0&&(!((-temp)%2)))
             count = 32 - count;         
         return count;
     }
};



发表于 2021-02-19 23:36:48 回复(0)
星夜。头像 星夜。
本题采用位运算的方式来进行解题
    拿1100为例
    首先我们把1100-1，此时我们的数就变成了1011
    我们再把1011与1100相与，此时得出1000
    由此看出 当我们二进制出现1的时候他就可以一直循环下去，知道我们的n变为0
public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
           n=n&(n-1);
           count++; 
        }
       return count;
        
    }
}


发表于 2021-02-12 12:59:36 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

二进制中1的个数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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