520
推荐
writezen
public class So
查看全部
编辑于 2015-08-18 23:23:00
回复(148)
1344
菩提旭光
绝对最佳答案及分析：
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)
3
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)
2
Python
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)
2
Python
刀轻城_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)
2
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)
2
JavaScript
Zfirsty
//Javascript 描述
function NumberOf1(n)
{
var num=0;
while(n){
num++;
n=(n-1)&n;
}
return num;
}
发表于 2017-07-28 11:27:16
回复(0)
2
Java
唐宋元明清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)
2
Java
牛油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)
1
C++
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)
1
99岁熬夜造bug
#include
发表于 2022-07-29 19:46:36
回复(0)
1
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)
1
Python
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< # count += 1 # 解法2 if n != 0 : n = (n-1)&n count += 1 return count 发表于 2021-06-12 04:12:42 回复(0) 1 C/C++ 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) 1 小写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) 1 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) 1 C/C++ 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) 1 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) 1 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) 1 星夜。 本题采用位运算的方式来进行解题 拿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) 1 Java 路平 public class Solution { public int NumberOf1(int n) { int count=0; //n&（n-1）会消去n的二进制的最后一个1 while(n!=0){ count++; n=n&(n-1); } return count; } } 发表于 2021-02-05 17:01:32 回复(0)