一. 题目

二. 理论

• 思路：位运算算法利用二进制位的操作来处理数据，通常涉及操作符如与(&)、或(|)、非(~)、异或(^)、左移(<<)和右移(>>)。这些操作在计算机底层实现上非常高效，常用于各种算法优化中。

• 时间复杂度：O(1)

• 本题思路：数列中元素的值最大为1e9, 2^30为1073741824，所以右移至0~30位即可，每次右移都&1判断当前位是否为1，若为1则当前值二进制表示1的个数加1。

• 或者利用x&-x求x的最后一位1。

三. 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;

int n;
int a[N];

//位运算类
class BitwiseOperations
{
public:
    static void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    /**
     * [1] 返回x的二进制的最后一位1
     * [2] 判断一个数是否为 2 的幂：如果一个数是 2 的幂，
     * 那么它的二进制表示中只有一位是 1。这时 x & -x 等于 x 本身。
     * @param x
     * @return 如上
     */
    int lowbit(int x)
    {
        return x&-x;
    }

    int work(int x)
    {
        int cnt=0;
//        for(int i=0;i<31;++i)
//            if(x>>i&1)
//                ++cnt;
        while(x)
        {
            ++cnt;
            x-= lowbit(x);
        }
        return cnt;
    }
};

int main()
{
    BitwiseOperations::initIO();

    cin>>n;
    BitwiseOperations bitwiseOperations;
    for(int i=0;i<n;++i)
    {
        int x;
        cin>>x;
        int ans=bitwiseOperations.work(x);
        cout<<ans<<" ";
    }
}