正经题解｜ 二进制下1的个数

题目分析

这道题做法有很多，下面列举部分。

方法一：可以使用二进制运算，每次取二进制中的最后一位，看是否为一。

方法二：每次&上 $n-1$，消除二进制中最右边的 $1$。

方法三：使用 bitset 容器，用 count 方法直接求。

AC 代码

方法一

#include <iostream>
using namespace std;

int main(){
    int n, cnt = 0; cin >> n;
    while(n){
        if (n & 1) 
            cnt++;
        n >>= 1;
    }
    cout << cnt << endl;
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}
int main() {
	int n;
	cin >> n;
	cout << countOnes(n) << endl;
	return 0;
}

方法三

#include <bits/stdc++.h>
#include <bitset>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << bitset<31>(n).count() << endl;
	return 0;
}

复杂度分析

每次运算的次数与 $1$ 的个数有关，设 $1$ 的个数为 $N$，复杂度为 $O(N)$。