CSP-J 2021 第一轮 第 21 题：程序（一）：输入2 -65536 2147483647的输出

题目

#include <iostream>
using namespace std;

int n;
int a[1000];

int f(int x)
{
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}

int g(int x)
{
    return x & -x;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++)
        cout << f(a[i]) + g(a[i]) << ' ';
    cout << endl;
    return 0;
}

当输入为 2 -65536 2147483647 时，输出为（ ）。

选项

• A. 65532 33
• B. 65552 32
• C. 65535 34
• D. 65554 33

答案

B

题解

答案选 B：65552 32。按题目默认的 32 位补码整数计算。

先看两个函数的作用：

• f(x)：统计二进制中 1 的个数。每执行一次 x &= x - 1，就会消去最低位的一个 1，因此循环次数就是 1 的个数。
• g(x)：x & -x 保留最低位的一个 1，其余位变成 0，返回这一位对应的数值。

① 对于 -65536

它的 32 位补码是： ``text 11111111 11111111 00000000 00000000 ``

有 16 个 1，最低的 1 位于第 16 位（从第 0 位开始计数），对应 \(2^{16}=65536\)。

所以： ``text f(-65536) + g(-65536) = 16 + 65536 = 65552 ``

② 对于 2147483647

它等于 \(2^{31}-1\)，二进制是： ``text 01111111 11111111 11111111 11111111 ``

有 31 个 1，最低位就是 1，所以： ``text f(2147483647) + g(2147483647) = 31 + 1 = 32 ``

因此输出为： ``text 65552 32 ``