二进制中1的个数
题目 二进制中1的个数
思路分析
一个int类型的变量有32位，想要取出第i位就是n >> i & 1
1的二进制是000…01 所以和任何数进行&运算结果都只可能是0或1
那么直接是0就加0 是1就加1 等同于对1做了一个计数
然后可以控制次数 直接写死32位
也可以每轮取出最后一个后 把x右边划掉一个
用while(x)写
当然还可以直接用lowbit()
x&-x
bitset也行
代码实现
//解法1
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i ++)
res += n >> i & 1;//如果n的第i位是1，则res+1；否则什么也不会发生
return res;
}
};
//解法2
class Solution {
public:
int NumberOf1(int n) {
unsigned int x = n;
int res = 0;
while (x) res += x & 1, x >>= 1;
return res;
}
};
//解法3
class Solution {
public:
//返回x的lowbit值
int lowbit(int x)
{
return x & (-x);
}
int NumberOf1(int n) {
int res = 0;
while (n)
{
n -= lowbit(n);//每次减去lowbit(n)
res ++;
}
return res;
}
};
💬 评论