AcWing 801：二进制中 1 的个数 ← lowbit 等三种算法

​【题目来源】
https://www.acwing.com/problem/content/803/

【题目描述】
给定一个长度为 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 5

out:
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 5

out:
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 5

out:
1 1 2 1 2
*/

【参考文献】
https://www.acwing.com/solution/content/183323/
https://www.acwing.com/solution/content/2370/




 

​