算法
(位运算) O(logn)
迭代进行如下两步，直到 n 变成0为止：
- 如果 n 在二进制表示下末尾是1，则在答案中加1；
- 将 n 右移一位，也就是将 n 在二进制表示下的最后一位删掉；
这里有个难点是如何处理负数。
在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 n 永远不为0，就死循环了。
解决办法是把 n 强制转化成无符号整型，这样 n 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。
时间复杂度
每次会将 n 除以2，最多会除 logn 次，所以时间复杂度是 O(logn)。
C++ 代码
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int un = n;
while (un) res += un & 1, un >>= 1;
return res;
}
};
甚至可以更简单
#include <bitset> class Solution { public: int NumberOf1(int n) { return bitset<32>(n).count(); } };太秀了
int占32位，直接循环32次
class Solution { public: int NumberOf1(int n) { int res = 0, t; for(int i = 0; i < 32; i++) { //int类型占4B即32bit，故循环32次 res += n >> i & 1; //n = n>>1; } return res; } };res += n >> i & 1;
可以解释一下这一行吗？我去查了运算符的优先级，也没看懂
假设
n = 100111111,i = 6则
n >> i = 100100& 1000故
n >> i & 1 = 0这个算式就是在算这一位是否为
1，若为1则+1.你这个最易懂了！
class Solution { public: int NumberOf1(int n) { int lowbit , cnt = 0; while(n) { lowbit = n & -n; cnt += 1; n &= ~lowbit; } return cnt; } };每次取出最低位的比特位，然后在n中去掉最低位比特
class Solution { public: int NumberOf1(int n) { int ans=0; while(n) { ans++; int t=n&-n; n -= t; } } };xdm,为啥这样写过不了呢,基础课里可以过啊,求教
你不return怎么过....
第一次做 ,没注意
为什么把n强制转换成unsigned后二进制表示不会改变呢，不是补码二进制表示吗
详细见 csapp，这里大概说一下
大部分语言实现的类型转换，底层二进制是不变的，只是改变了二进制位的解释
无符号类型的右移是逻辑右移，即高位补 0
数据类型是给人看的，就像你随便找个文件，把文件后缀改了，内容并不会变
class Solution { public: int NumberOf1(int n) { int res=0; for(int i=n;i;i-=i&-i) res++; return res; } };lowbit时间复杂度也算O(logn)吧
这是甚么意识！！呜呜
lowbit好用呀
意识流打法nb啊
确实好用
class Solution { public: int NumberOf1(int n) { int res=0,a=1; while(a){ if(n&a) res++; a<<=1; } return res; } };太厉害了
tql大佬
太厉害了👍
orz,运动是相对的....
class Solution { public: int NumberOf1(int n) { auto ret = 0; // 1 oneway // while (n) { // ret += 1; // int val = n & -n; // n -= val; // } while (n) { ret += 1; n &= (n - 1); } return ret; } };class Solution{这是什么意思呀，我只知道include
C++:
class Solution {
public:
int NumberOf1(int n) {
return __buildin_popcount(n);
}
};
是builtin
class Solution {
public:
int NumberOf1(int n) {
int res=0;
while(n!=0)
{
res++;
n&=n-1;
}
return res;
}
};
运行时间:11ms
class Solution {
public:
int NumberOf1(int n) {
int i = n;
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
};
class Solution { public: int NumberOf1(int n) { int ans = 0; for (int i = n; n; n -= n & -n ) ans ++ ; return ans; } };直接位运算，3行结束
int x=0; for(int i=0,j=1;i<32;++i,j<<=1) x+=(bool)(j&n); return x;class Solution { public: int NumberOf1(int n) { int cnt = 0; while (n) n &= n - 1, cnt++; return cnt; } };或者是
class Solution { public: int NumberOf1(int n) { return __builtin_popcount(n); } };_builtin_popcount可以是负数吗？
传入后强制转换为无符号整型。
我的方法太笨了[笑哭]
class Solution { public: int NumberOf1(int n) { int res=0,f=0; if(n==-1) return 32; if(n==-2147483648) return 1; if(n<0) n=-n,f=1; int m=n; while(n) { res+=n & 1; n >>= 1; } if(f==1 && m%2==0) return 32-res; else if(f==1 && m%2==1) return 32-res+1; return res; } };确实比较繁琐hh
n&1是什么
取最低位
为啥用lowbit计算，n=n-n&-n不能AC,而用n-=n&-n能AC啊？
减号的优先级高于
&。但是如果用同样的方法Java里没有无符号整型怎么办呢，还有没找到怎么贴代码框的地方🤣
class Solution { public int NumberOf1(int n) { int num = 0; while(n ！= 0){ num += n & 0x01; n /= 2; } return num; } }可以强行循环32次。
评论里也是markdown语法，代码前后加上三个```，就能正常显示了。
但是java有无符号右移啊
class Solution { public int NumberOf1(int n) { int ans = 0; while (n != 0) { ans += n & 1; n >>>= 1; } return ans; } }niubi
func NumberOf1(n int) int { count:=0 for n!=0 { n = n & n-1 count++ } return count } func NumberOf1(n int) int { count:=0 for n!=0 { n &= n-1 count++ } return count }go 语言为什么第一种方式不行，第二种方式可以？
运算符优先级的问题，在golang里&的优先级比减号高，给
n - 1加上括号就行了。class Solution { public: int NumberOf1(int n) { int res = 0; while (n) { n -= n & -n; res += 1; } return res; } };这是算法基础课里讲到的方法，在这也可以通过
好滴，很棒～
这个写的就很棒！