首页 > 试题广场 > 二进制中1的个数
[编程题]二进制中1的个数
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
推荐
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 回复(121)
绝对最佳答案及分析:
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 回复(161)
看了很久都没有Python实现的,那我来一个
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n < 0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n - 1) & n
        return count

发表于 2017-07-07 14:55:47 回复(50)

python一行解法:
如果n大于0,直接计算即可,如果n小于0,计算2的32次方加上n的结果中1的个数。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        return bin(n).replace("0b","").count("1") if n>=0 else bin(2**32+n).replace("0b","").count("1")
编辑于 2017-09-11 08:59:26 回复(21)
首先判断n是不是负数,当n为负数的时候,直接用后面的while循环会导致死循环,因为负数
向左移位的话最高位补1 ! 因此需要一点点特殊操作,可以将最高位的符号位1变成0,也就
是n & 0x7FFFFFFF,这样就把负数转化成正数了,唯一差别就是最高位由1变成0,因为少了
一个1,所以count加1。之后再按照while循环里处理正数的方法来操作就可以啦!
class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         if(n < 0){
             n = n & 0x7FFFFFFF;
             ++count;
         }
         while(n != 0){
             count += n & 1;
             n = n >> 1;
         }
         return count;
     }
};

编辑于 2016-06-06 17:13:19 回复(22)
public class Solution {
    public int NumberOf1(int n) {
        return Integer.toBinaryString(n).replaceAll("0","").length(); }
}

编辑于 2016-02-02 19:10:47 回复(43)
class Solution {
public:
     int  NumberOf1(int n) {
        return bitset<32>(n).count();
     }
};//
编辑于 2018-07-19 11:53:40 回复(10)
java自带的函数
public class Solution {
public int  NumberOf1(int n) {
         return Integer.bitCount(n);
     }
}
发表于 2016-07-24 16:20:06 回复(21)
public class Solution {
public int  NumberOf1(int n) {
          int temp = n;
 temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa) >>> 1);
 temp = (temp & 0x33333333) + ((temp & 0xcccccccc) >>> 2);
 temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >>> 4);
 temp = (temp & 0x00ff00ff) + ((temp & 0xff00ff00) >>> 8);
 temp = (temp & 0x0000ffff) + ((temp & 0xffff0000) >>> 16); 
 return temp;
     }
}
//之前的习题
发表于 2016-06-04 16:11:17 回复(12)
public class Solution {
    public int NumberOf1(int n) {
        int sum=0;
        while(n!=0){
            sum+=n&1;//逐个判断低位是否为1;
            n=n>>>1;//无符号右移,例如从11101变成1110
        }
		return sum;
    }
}

发表于 2016-11-10 18:34:06 回复(6)
//超级简单容易理解                            //&(与)
// //把这个数逐次 右移 然后和1 与,
//就得到最低位的情况,其他位都为0,
//如果最低位是0和1与 之后依旧 是0,如果是1,与之后还是1。
//对于32位的整数 这样移动32次 就记录了这个数二进制中1的个数了 

class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         for(int i=0;i<32;i++){
            if(n>>i&1)  
                count++;  
         }
         return count;
     }
};
发表于 2016-05-29 17:22:25 回复(10)
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        '''
        f=1
        c = 0
        for _ in range(32):
            if f&n>=1:
                c+=1
            f = f<<1
        return c
        '''
        c = 0
        if n<0:
            n = n&0xffffffff
        while n:
            c += 1
            n &= n-1
        return c
因为python的int是无线精度的,c++的int是32为的,所以python的负数相当于前面有无限个1,要对python的负数做处理
发表于 2018-04-14 21:29:33 回复(3)
function NumberOf1(n)
{
    //js中负数使用二进制补码的形式存储
    if(n < 0){
        //无符号右移将负数的二进制码当成正数的二进制码
        n = n >>> 0;  
    }
    var arr = n.toString(2).split('1');
    return arr.length-1;
}

发表于 2018-04-12 17:18:02 回复(3)
public int NumberOf1(int n) {
        String s=null;
        if(n<0){
             s=Integer.toBinaryString(~(-n)+1);//负数的补码等于负数的绝对值取反。
        }else{
             s=Integer.toBinaryString(n);
        }
        char[] num=s.toCharArray();
        int x=0;
        for(int i=0;i<num.length;i++){
            if(num[i]=='1'){
                x++;
            }
        }
        return x;
    }
发表于 2017-09-13 17:48:37 回复(1)
Ron头像 Ron
public class Solution {
    public int NumberOf1(int n) {
		int count=0;
		for(count = 0;n!=0;count++){
			n=n&(n-1);
		}
		return count;
    }
}
发表于 2015-08-20 18:48:35 回复(5)
时间复杂度为O(n)
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        num = n
        flag = 1
        count = 0
        while flag<=0xffffffff:
            if num & flag:
                count += 1
            flag = flag << 1
        return count
  
C语言中循环结束应该是flag==0,但是python 整数存取的时候没有位数限制。
class Solution:
     def NumberOf1(self, n):
        count=0
        if n<0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = n&(n-1)
        return count

发表于 2018-05-12 16:44:24 回复(0)
一次惨败的面试经历,却学会了一串代码
public class Solution {
    public int NumberOf1(int n) {
        int result=0;
        int test=n;
        while (test!=0){
            test&=(test-1);
            result++;
        }
        return result;
    }
}

编辑于 2017-10-11 09:18:17 回复(0)
关键是负数吧,在C++中,有符号整数右移(算术右移)是最高位补符号位的,比如 -1 >> 1 其实是 -1,转成unsigned int 就可以了。
在java中,没有unsigned这个东西,但是有 逻辑右移 >>> 运算符。。。

c++版暴力计数(循环次数等于n的二进制长度,如n=257循环9次):
class Solution {
public:
     int  NumberOf1(int n) {
         for(unsigned int r = 0, m = n; ; r += m & 1, m >>= 1) if(m == 0) return r;
     }
};



利用lowbit优化(循环的次数等于n的二进制中1的个数,如n=257循环2次)
class Solution {
public:
     int  NumberOf1(int n) {
         for(unsigned int r = 0, m = n; ; ++r, m -= m & -m) if(m == 0) return r;
     }
};



编辑于 2015-08-22 22:07:23 回复(0)
class Solution {
public:
     int  NumberOf1(int n) {
         bitset<32> bit(n);
         return bit.count();
     }
};
不解释了 = =
发表于 2015-09-02 22:48:31 回复(3)
/**
 * 思路:将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)

最简单的方法。整数n每次进行无符号右移一位,检查最右边的bit是否为1来进行统计即可。

int count1(int n)
{
    unsigned int num = (unsigned)n;
    int res = 0;
    while(num != 0)
    {
        res += num & 1;
        num = num >> 1;
    }
    return res;
}

上述方法最坏情况下要进行32次循环,接下来介绍两个循环次数只与1的个数有关的解法。

int count2(int n)
{
    int res = 0;
    while(n != 0)
    {
        n -= n & (~n + 1);
        res++;
    }
    return res;
}

每次进行n -= n & (~n + 1)操作时就是移除最右边1的过程。n & (~n + 1)的含义就是得到n中最右边的1。例如,n = 01000100, n & (~n + 1) = 00000100, n - n & (~n + 1) = 01000000。

int count3(int n)
{
    int res = 0;
    while(n != 0)
    {
        n = n & (n-1);
        res++;
    }
    return res;
}

n = n & (n-1)这也是移除最右侧1的过程。例如: n = 01000100, n-1 = 01000011, n & (n-1) = 01000000。

发表于 2017-12-02 11:22:40 回复(0)