CSP-J 入门级 · CSP 2026 入门级第一轮 第 16 题

【阅读程序1】

以下问题均假定输入的 n 为不超过 2^31 - 1 的非负整数。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int x = 1, y = 1;
    while (n > 0) {
        if (n % 2 == 0) {
            ++x;
        } else {
            ++x;
            ++y;
        }
        n = n / 2;
    }
    cout << x << ' ' << y << endl;
    return 0;
}

关键看第 11、12 行：if 分支和 else 分支各有一个 ++x（第 11 行在 else 里），所以每轮循环 x 必加 1；而 ++y（第 12 行）只在最低位为 1 时执行。于是 x = 二进制位数 + 1，y = popcount(1 的个数) + 1。

把第 11、12 行看漏一行，误以为 x、y 分别统计"0 的个数"和"1 的个数"而没有 +1；或忘记 n = 0 时循环一次都不执行（x = y = 1）。第 21 题还容易把 popcount 为 1 的数漏掉 2^0 = 1。

程序分析

核心代码（第 6～16 行，以原卷为准）：

int x = 1, y = 1;
while (n > 0) {
    if (n % 2 == 0) {
        ++x;          // 第 9 行：最低位是 0
    } else {
        ++x;          // 第 11 行：最低位是 1 时也要 +1
        ++y;          // 第 12 行：只有最低位是 1 才 +1
    }
    n = n / 2;        // 第 14 行：整体右移一位
}
cout << x << ' ' << y;

两条关键结论（把这段程序吃透，六道小题都能秒答）：

1. 每一次循环必定执行一次 ++x（两个分支各有一个），所以 x = 循环次数 + 1 = n 的二进制位数 + 1（n = 0 时循环 0 次，x = 1）。 2. ++y 只在最低位为 1 的分支执行，所以 y = n 的二进制中 1 的个数（popcount）+ 1。 3. 因为 popcount ≤ 位数，恒有 x ≥ y；两者相等当且仅当 n 的二进制全是 1（如 1、3、7…）或 n = 0。

第 16 题（判断）

n = 3 = 11₂：位数 = 2 → x = 3；popcount = 2 → y = 3。输出 3 3，题述"输出为 3 3"正确。 答案：A（正确） ✓

验算循环：n=3>0 → else 分支 x=2,y=2，n=1；n=1>0 → else 分支 x=3,y=3，n=0；循环结束 → 3 3 ✓

第 17 题（判断）

删去第 11 行的 ++x; 后，x 只在"最低位是 0"时累加，于是 x = (n 的二进制中 0 的个数) + 1，y = popcount + 1。 两者相等需要"0 的个数 = 1 的个数"。取 n = 3（11₂，0 个 0）：x = 1、y = 3，不相等。 所以"一定相等"的说法错误。 答案：B（错误） ✓

第 18 题（判断）

由结论 3，对一切非负整数都有 x ≥ y（n = 0 时取等号），因此"第一个数一定不小于第二个数"正确。 答案：A（正确） ✓

第 19 题（单选）

把 while (n > 0) 改成 while (n >= 0)：因为 n 始终是非负整数，n = n / 2 在 n 已经为 0 后仍是 0，条件 0 >= 0 永远成立 → 陷入死循环。 答案：A（陷入死循环） ✓ （B、C 都不会发生：死循环下程序根本没有输出；D 更是错，循环条件改了行为必然改变。）

第 20 题（单选）

n = 6 = 110₂：位数 = 3 → x = 4；popcount = 2 → y = 3。输出 4 3。 答案：C（4 3） ✓

循环轨迹：n=6 偶 → x=2；n=3 奇 → x=3,y=2；n=1 奇 → x=4,y=3；n=0 结束。

第 21 题（单选）

第二个数 y = popcount(n) + 1，要求 y = 2，等价于 popcount(n) = 1，即 n 恰好是 2 的幂（二进制只有一个 1）。 n 的取值范围是 0 … 2³¹ − 1：

• n = 0 的 popcount = 0（y = 1），不符合；
• n = 2⁰, 2¹, …, 2³⁰ 共 31 个数符合。

答案：C（31） ✓ （易错点：漏掉 2⁰ = 1，或误以为要算 2³¹ = 2147483648 而它已超出 int 范围。）

本题小结

套路提示：这类"统计二进制位数 / 1 的个数"的程序题，先写清"每个变量各在什么条件下 +1"，再套 popcount / 位数的结论，几乎不需要真的逐轮模拟。