给定一个长度为 n
的数列,请你求出数列中每个数的二进制表示中 1
的个数。
输入格式
第一行包含整数 n
。
第二行包含 n
个整数,表示整个数列。
输出格式
共一行,包含 n
个整数,其中的第 i
个数表示数列中的第 i
个数的二进制表示中 1
的个数。
数据范围
1≤n≤100000
,
0≤数列中元素的值≤109
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2
思路:
二进制题目中最常见的操作
查看数字当前第k位的数字是几?
以图上的数字排序为例子
我们想查看一个数字第几位的数字 就可以用下面的方式
num>>k & 1
树状数组的基本操作
功能 是返回 当前数字的最后一位1
比如数字 x=110100 返回的就是第2位 1
lowbit(x)=100
lowbit 具体实现
源码: return (x & -x)
-x =~x +1
x &(~x +1)
个人思路
#include<iostream>
using namespace std;
int main()
{
int n ;
cin>>n;
for(int i= 0; i < n;i++)
{
int tmp = 0 ;
cin >> tmp;
int num=0;
while(tmp != 0)
{
if(tmp & 1)
num++;
tmp>>=1;
}
cout<<num<<" ";
}
return 0;
}
y总思路
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
int x, s = 0;
scanf("%d", &x);
//lowbit 每次减去最后一位数字 来计算 它有多少个1
for (int i = x; i; i -= i & -i) s ++ ;
printf("%d ", s);
}
return 0;
}