中级 · 位运算

数一数 1 的个数

一个数的二进制里有多少个 1？这叫 popcount，而且它在真实 CPU 里是一条指令。

一句话答案每次把 n 右移一位并累加 n & 1 来数 1 的个数 —— 或者用 n &= n - 1 每步清掉一个 1，循环次数正好等于 1 的个数。

题目

输入: 一个非负整数（0 <= n <= 1000000）。

输出: n 的二进制中 1 的个数。

样例:

输入输出
73

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 把余数加起来

n > 0 时：ones += n % 2; n /= 2;。二进制表示里打印的余数就是这些位。

提示 2 — Kernighan 技巧

while (n) { n &= n - 1; ones++; } 每圈清掉最低位的 1 —— 循环次数等于 1 的个数。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ones = 0;
    while (n > 0) {
        ones += n % 2;
        n /= 2;
    }
    cout << ones << endl;
    return 0;
}

现代 C++ 有 std::popcount(n)（C++20），编译成一条 CPU 指令。你刚手写了一遍它。

深度解析

为什么这样做对

数 1 的三种写法——移位判断、Kernighan 的 n&(n-1)、硬件 popcount——正好是一次「同一答案、三种代价」的速览。

代价

朴素：恒定 32 轮。Kernighan：轮数等于 1 的个数。硬件：一条指令 O(1)。

常见错法

  • 对有符号负数右移是实现定义行为，符号位会被不断补回来，循环可能永不结束。
  • n >>= 1 用在负数上永远到不了 0。用 unsigned。

下一步

让这些位派上用场：二进制表示。

记住这两句

  • Kernighan：按 1 的个数循环，不是按位数循环。
  • 只对无符号数移位——有符号右移是实现定义行为。
🐞 这段是错的 —— 点开,亲手让它挂一次

只数了低 8 位，大数就漏了

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int c = 0;
    for (int i = 0; i < 8; i++) {
        if (n % 2 == 1) c++;
        n /= 2;
    }
    cout << c << endl;
    return 0;
}