AcWing 801. 二进制中1的个数(全网最简单)
原题链接
简单
作者:
不认输蒟蒻小小牛
,
2021-10-05 12:52:20
,
所有人可见
,
阅读 1017
题目描述
戳我戳我!!
样例
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2
数据范围
1≤n≤100000,
0≤数列中元素的值≤109
基本思想
用 x & -x 返回 x 中最后一位 1。比如对于0…01001000(32位)返回1000,对于0…010110100(32位)
返回100。每一次减掉最后一位1,看总共减了几次就能得到二进制有几个1。
y总视频讲解
y总视频讲解
步骤
①写一个lowbit函数返回 x & -x。
②循环减去最后一位1,并计数。
AC代码
#include <bits/stdc++.h>
using namespace std;
int lowbit(int x){ return x & -x;}
int main(){
int n;
cin>>n;
while(n--){
int x,res=0;
cin>>x;
while(x){ x-=lowbit(x),res++;}
cout<<res<<" ";
}
return 0;
}
致谢
acwing官网。
最后
看在我第1次的份上
点个支持+收藏
如果有问题私信哟
(^U^)ノ~YO
加油!!!!!
用bitset,三行就好了
是挺简单的,很好理解!谢谢!
加油,兄弟
/kk 就这?全网最短?你开玩笑呢?
缩缩行