lowbit(x)
题目 二进制中1的个数
思路分析
返回x的最后一位1
内部实现很简单
int lowbit(x){
return x&-x;
}
这个x&-x等价于 x&(~x+1)
假设
x=1010……1000……
~x=0101……0111……
~x+1=0101……1000……
将x&(~x+1)得0000……1000……
也就是只保留从右边数第一个1 其他全变成了0
然后就可以利用这个性质 求某二进制序列中有多少个1（一直循环直到没有就行了）
int x; cin>>x;
int res=0;
while(x){ x-=lowbit(x); res++;}
如此可得x中1的个数
代码实现
#include<bits/stdc++.h>
using namespace std;
//const int N=100010;
//int q[N];
int lowbit(int x)
{
return x&-x;
}
int main()
{
int n;
cin>>n;
while(n--)
{
//无需多此一举存入数组 读入一个数就立即对它操作就好了
int x;
cin>>x;
int res=0;
while(x)
{
x-=lowbit(x);
res++;
}
cout<<res<<" ";
}
return 0;
}
💬 评论