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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √ ，错误填 × ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

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

判断题

16. 输入的 $n$ 等于 $1001$ 时，程序不会发生下标越界。（ ）

17. 输入的 $a[i]$ 必须全为正整数，否则程序将陷入死循环。（ ）

18. 当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。（ ）

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

20. 将源代码中 g 函数的定义（$14\sim 17$ 行）移到 main 函数的后面，程序可以正常编译运行。（ ）

单选题

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

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

f(x)计算二进制中1的个数(bit count)，g(x)=x&-x取最低位的1。f(a[i])+g(a[i])即1的个数+最低位1的值。

注意x&-x是lowbit运算（取最低位的1）。例如6的二进制110，lowbit(6)=2。函数f中的x&=x-1是经典操作，每次消去最低位的1，ret统计消去次数即为1的个数。

考察知识点：位运算 — lowbit与popcount

程序分析：

int f(int x) {  // 统计x的二进制中1的个数
    int ret = 0;
    for (; x; x &= x - 1) ret++;
    return ret;
}

int g(int x) {  // 取x的最低位的1（lowbit）
    return x & -x;
}

f函数：每次x&=x-1消去最低位的1，循环次数=1的个数 g函数：x&-x = x的反码+1再与x = 最低位1的值

逐题解析： 16. ❌ n=1001时，a数组只有1000个元素，访问a[1000]越界 17. ❌ a[i]为负时二进制仍可正常运算（补码），不会死循环 18. ❌ 输入5 2 11 9 16 10，输出应为3 4 3 17 5？需要逐项计算。 19. ✅ 输入1 511998，511998的二进制1的个数+lowbit值=18 20. ❌ g函数在main之后定义但main中调用了g，需要前向声明 21. 输入2 -65536 2147483647，分别计算f+g的值