二进制中1的个数

5
1 2 3 4 5

样例

1 1 2 1 2

算法1

$O(1)$

判断1~n二进制中1个数的方法
1：for(int j = 0; j < n; j)
if(i & (1 << j) res;
//代码

2: for(int i = 0; i < n; i)
{
int kk = i;
while(kk)
{
kk = kk &(kk - 1);res;
//代码
}
}

时间复杂度

参考文献

算法竞赛入门

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], res[N];
int main(){
    int n; cin >> n;
    for(int i = 0;i < n; ++i){
        cin >> q[i];
        while(q[i]){
            q[i] = q[i] & (q[i] - 1);
            res[i] ++;
        }
    }
    for(int i = 0; i < n; ++i)cout << res[i] << " ";
    return 0;
}