题目描述
给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。
输入格式
第一行包含整数n。
第二行包含n个整数，表示整个数列。
输出格式
共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。
数据范围
1≤n≤100000,
0≤数列中元素的值≤109
样例
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
算法1
(lowbit) O(nlogn)O(nlogn)
使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数，
lowbit原理
根据计算机负数表示的特点，如一个数字原码是10001000，他的负数表示形势是补码，就是反码+1，反码是01110111，加一则是01111000，二者按位与得到了1000，就是我们想要的lowbit操作
C++ 代码
#include using namespace std; 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;
}
算法2
(暴力枚举) O(nlongn)O(nlongn)
blablabla
时间复杂度分析：blablabla
思路
对于每个数字a，a&1得到了该数字的最后一位，之后将a右移一位，直到位0，就得到了1的个数
C++ 代码
#include using namespace std; int n; int a,k; int main(){ scanf(“%d”,&n); for(int i=0;i<n;i++){ scanf(“%d”,&a); k=0; while(a){ k+=a&1; a=a>>1; } printf("%d ",k); } return 0; }
笔记：
位运算是个好东西可惜我不会用。
这个帖子适合位运算中有一定基础的童鞋们看。
大佬别来虐场
求nn的二进制位表示中第kk为是几？
把第kk位移动到最后一位。
看各位
得出公式n>>k&1
返回nn的最后一位11。
也就是求解lowbit(n)lowbit(n)。
求解过程：n&(-n)
统计nn的二进制表示中11的个数（本题）？
while(n) ans++, n -= lowbit(n);
代码：
#include <bits/stdc++.h> using namespace std; int lowbit(int x) { return x & (-x); } int main() { int t, x; cin>>t; while (t–) { cin>>x; int ans = 0; while (x) ans ++, x -= lowbit(x); cout << ans << " "; } return 0; }
题目描述
给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。
输入格式
第一行包含整数n。
第二行包含n个整数，表示整个数列。
输出格式
共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。
数据范围
1≤n≤100000,
0≤数列中元素的值≤109
样例
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
算法1
(lowbit) O(nlogn)O(nlogn)
使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数，
lowbit原理
根据计算机负数表示的特点，如一个数字原码是10001000，他的负数表示形势是补码，就是反码+1，反码是01110111，加一则是01111000，二者按位与得到了1000，就是我们想要的lowbit操作
C++ 代码
#include using namespace std; 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;
}
算法2
(暴力枚举) O(nlongn)O(nlongn)
blablabla
时间复杂度分析：blablabla
思路
对于每个数字a，a&1得到了该数字的最后一位，之后将a右移一位，直到位0，就得到了1的个数
C++ 代码
#include using namespace std; int n; int a,k; int main(){ scanf(“%d”,&n); for(int i=0;i<n;i++){ scanf(“%d”,&a); k=0; while(a){ k+=a&1; a=a>>1; } printf("%d ",k); } return 0; }
