【题目来源】
【题目描述】
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
【输入格式】
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。
【输出格式】
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
【输入样例】
5
1 2 3 4 5
【输出样例】
1 1 2 1 2
【数据范围】
1≤n≤100000,
0≤数列中元素的值≤10^9
【算法分析】
● 短除法是一种用于整数除法的简便算法，尤其适用于进制转换。它的核心思想是“除基取余，倒序排列”。
● 位运算法。基于“>>=”、“&”等位运算操作，进行统计。
● lowbit(x)=x & (-x)，返回整数的二进制表示中最低位 1 所对应的十进制数。
【算法代码一：模拟短除法】
短除法是一种用于整数除法的简便算法，尤其适用于进制转换。它的核心思想是“除基取余，倒序排列”。
#include <bits/stdc++.h>
using namespace std;int main() {int n,x,cnt;cin>>n;while(n--) {cnt=0;cin>>x;while(x) {if(x%2==1) cnt++;x/=2;}cout<<cnt<<" ";}return 0;
}/*
in:
5
1 2 3 4 5out:
1 1 2 1 2
*/
【算法代码二：位运算法】
基于“>>=”、“&”等位运算操作，进行统计。
#include <bits/stdc++.h>
using namespace std;int main() {int n,x,cnt;cin>>n;while(n--) {cnt=0;cin>>x;while(x) {if(x&1) cnt++;x>>=1;}cout<<cnt<<" ";}return 0;
}/*
in:
5
1 2 3 4 5out:
1 1 2 1 2
*/【算法代码三：lowbit】
lowbit(x)=x & (-x) 返回整数的二进制表示中最低位 1 所对应的十进制数。
例如，lowbit(1101000) 返回 8。
#include <bits/stdc++.h>
using namespace std;int lowbit(int x) {return x&(-x);
}int main() {int n,x,cnt;cin>>n;while(n--) {cnt=0;cin>>x;while(x) {cnt++;x-=lowbit(x);}cout<<cnt<<" ";}return 0;
}/*
in:
5
1 2 3 4 5out:
1 1 2 1 2
*/
【参考文献】