AC题解

要计算一个十进制非负整数 N 的二进制表示中 1 的个数，核心思路是逐位检查或利用位运算。

常用方法有两种：

逐位右移法

每次检查 N 的最低位（N & 1），如果为 1 则计数加 1。

然后将 N 右移一位（N >>= 1），继续检查新的最低位。

重复直到 N 变为 0。

时间复杂度为 O(log₂N)，适用于 N < 10⁹ 的范围。

利用 n & (n-1) 技巧

每执行一次 n = n & (n-1)，就会消除 n 的二进制中最右侧的一个 1。

循环执行，统计执行次数，直到 n 为 0。

循环次数等于 1 的个数，比方法一更快（尤其当 1 较少时）。

对于本题，因为 N 最多 10⁹（约 30 位），两种方法都足够。
示例（方法一）：N=100（二进制 1100100），过程：

100 & 1 = 0, 计数=0, 右移得 50

50 & 1 = 0, 右移得 25

25 & 1 = 1, 计数=1, 右移得 12

12 & 1 = 0, 右移得 6

6 & 1 = 0, 右移得 3

3 & 1 = 1, 计数=2, 右移得 1

1 & 1 = 1, 计数=3, 右移得 0
结束，输出 3。

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    int count = 0;
    while (N > 0) {
        count += N & 1;  // 检查最低位是否为1
        N >>= 1;         // 右移一位
    }
    cout << count << endl;
    return 0;
}