CSP-J 2021 第一轮 第 19 题：程序（一）：输入1 511998的输出

题目

#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;
}

当输入为 1 511998 时，输出为 18。（ ）

选项

• A. 正确
• B. 错误

答案

A

题解

选 A. 正确。关键是看懂 f 和 g 的作用。

1. f(x)：统计二进制中有多少个 1

每执行一次 x &= x - 1，就会把 x 的二进制中最右边的一个 1 变成 0。因此，循环次数就是 1 的个数。

511998 的二进制为（分组方便计数）：

``text 0111 1100 1111 1111 1110 ``

其中有 3 + 2 + 4 + 4 + 3 = 16 个 1，所以 f(511998) = 16。

2. g(x)：取出二进制中最右边的 1 所代表的值

x & -x 是常见的 lowbit 运算。511998 的二进制末尾为 10，最右边的 1 代表的值是 2，所以 g(511998) = 2。

输入中 n = 1，只处理一个数，输出为：

``text 16 + 2 = 18 ``

因此题目说法正确。（程序实际还会在 18 后输出一个空格，然后换行。）