CSP-J 2026 第一轮 第 21 题：程序（一）：若输入 n 依次取遍 0,1,2,…,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;
}

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

若输入 $n$ 依次取遍 $0, 1, 2, … , 2^{31}- 1$ 中的所有整数，则程序输出的第二个数恰好为 2 的次数为（ ）。

选项

• A. 16
• B. 30
• C. 31
• D. 32

答案

C

题解

答案是 C. 31。

循环中，n % 2 取出二进制的最低位，n = n / 2 则去掉这一位。因此，程序会依次检查原来的 n 的每一个二进制位。

y 初始为 1，只有遇到二进制位为 1 时才加 1，所以：

\[ y=1+n\text{ 的二进制表示中 1 的个数} \]

要让输出的第二个数恰好为 2，n 的二进制表示中就必须恰好有一个 1，也就是 n 必须是 2 的整数次幂：

\[ 2^0,2^1,2^2,\ldots,2^{30} \]

这些数都不超过 \(2^{31}-1\)，共 \(30-0+1=\boxed{31}\) 个。

注意：输入 n = 0 时不进入循环，输出的第二个数为 1，不计入。