CSP-J 2021 入门级 第一轮（初赛） 阅读程序（1）

【题目】

CSP-J 2021 入门级 第一轮（初赛） 阅读程序（1）

01 #include <iostream>
02 using namespace std;
03
04 int n;
05 int a[1000];
06
07 int f(int x)
08 {
09     int ret = 0;
10     for (; x; x &= x-1) ret++;
11     return ret;
12 }
13
14 int g(int x)
15 {
16     return x & -x;
17 }
18
19 int main()
20 {
21     cin >> n;
22     for (int i = 0; i < n; i++) cin >> a[i];
23     for (int i = 0; i < n; i++)
24         cout << f(a[i]) + g(a[i]) << ' ';
25     cout << endl;
26     return 0;
27 }

• 判断题：

1. 输入的n等于1001时，程序不会发生下标越界。（ ）
2. 输入的a[i]必须全为正整数，否则程序将陷入死循环。（ ）
3. 当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。（ ）
4. 当输入为 1 511998 时，输出为 18。（ ）
5. 将源代码中 g 函数的定义（14∼17 行）移到 main 函数的后面，程序可以正常编译运行。（ ）

• 单选题:

6. 当输入为 2 -65536 2147483647 时，输出为（ ）。
   A. 65532 33
   B. 65552 32
   C. 65535 34
   D. 65554 33

【题目考点】

1. 位运算

2. 机器数

【解题思路】

先看f函数

07 int f(int x)
08 {
09     int ret = 0;
10     for (; x; x &= x-1) ret++;
11     return ret;
12 }

第10行的意义为：只要x不为0，就进行循环每次循环让x变为x & x-1的值。
已知内存中以补码形式保存数值。
-1的原码为:10...01
-1的反码为:11...10（除了符号位，各位取反）
-1的补码为:11...11（反码加1）

对一个数的补码减1与加-1得到的结果相同。

先考虑x不为0的情况。
设x的补码为
PD...(x位)...D10...(y位)...0
首先P是符号位，而后有x位，每位可能相同也可能不同，暂且都用D表示（不代表标记为D的这些位都相同）。由于x不为1，那么其中必然存在某一位为1。该数最后一位1后面有y位0（y可能为0）。
现在进行计算：x-1，也就是x加上-1。-1的补码每一位都是1，也就是要将x的每一位都增加1。
原数最后一位1后面的y位0变为y位1。
原数最后一位1加1后变为0，进位1。
对于最后一位1前面的每一位，需要加上-1的补码提供的1，以及后面进位过来1。该位加2后的值不变，进位1。
包括最高位符号位，也加上了-1的补码提供的1，以及后面进位过来1，该位加2后值不变，进位1，但进位溢出了，超出了机器数的范围，不起作用。
因此x-1的补码为：
PD...(x位)...D01...(y位)...1
其实，和x的补码在二进制下直接减1得到的值是一样的。

而后进行x & x-1位运算。
已知1&1=1, 0&0=1, 0&1=0, 1&0 = 0，那么有D&D = D。
列竖式：

   PD...(x位)...D10...(y位)...0
&  PD...(x位)...D01...(y位)...1
------------------------------------------PD...(x位)...D0...(y+1位)..0

x & x-1的结果相比于x，最低位的1变成了0。

每进行一次循环，x都变为x & x-1，x的补码最低位的1变为了0，或者说减少了一位1。每次循环ret增加1。当x每一位都是0时，x的值为0，跳出循环。因此ret的值为x的补码中1的位数。
当f函数传入的x值为0时，其补码为00…0，不会进入循环，ret为0，仍然满足：ret表示x中1的位数。
因此f(x)的意义是求x的补码中1的位数（x的补码中有多少位1）。

14 int g(int x)
15 {
16     return x & -x;
17 }

设x为正数：
记x的补码为：0D...(x位)...D10...(y位)...0
最高位为0，而后有x位，每位的值可能不同，最后一位1后面有y位0，y可能为0。
-x的原码为：1D...(x位)...D10...(y位)...0
-x的反码为：1R...(x位)...R01...(y位)...1 (R表示D取反后的值。如果D为0，则R为1。如果D为1，则R为0）
-x的补码为：1R...(x位)...R10...(y位)...0
求 x & -x

    0D...(x位)...D10...(y位)...0 &  1R...(x位)...R10...(y位)...0----------------------------------- 0...(x+1位)..010...(y位)...0

得到的结果是x最低位1与后面的y位0合在一起构成的数值，也就是最低位1的位权。

设x为负数：
x的补码为：1D...(x位)...D10...(y位)...0
最高位为1，而后有x位，每位的值可能不同，最后一位1后面有y位0，y可能为0。
x的反码为：1D...(x位)...D01...(y位)...1
x的原码为：1R...(x位)...R10...(y位)...0 (R为D取反后的值)
-x的原码为：0R...(x位)...R10...(y位)...0
-x的补码为：0R...(x位)...R10...(y位)...0
求 x & -x

  1D...(x位)...D10...(y位)...0
& 0R...(x位)...R10...(y位)...0
---------------------------------- 0...(x+1位)..010...(y位)...0

得到的结果是x最低位1与后面的y位0合在一起构成的数值，也就是最低位1的位权。
当x为0时，x & -x为0，返回0，依然符合“最低位1的位权”的概念。
因此g(x)求的是x的补码中最低位1和后面的0组成的数值，也就是最低位1的位权。

19 int main()
20 {
21     cin >> n;
22     for (int i = 0; i < n; i++) cin >> a[i];
23     for (int i = 0; i < n; i++)
24         cout << f(a[i]) + g(a[i]) << ' ';
25     cout << endl;
26     return 0;

输入由n个整数构成的a数组，遍历a数组，对a中每个元素求其补码的1的位数与最低位1与后面的0构成的数值的加和，并输出。

• 判断题：

1. 输入的n等于1001时，程序不会发生下标越界。（ ）
答：F

05 int a[1000];

a数组长为1000，可以使用的下标范围为0到999。
当n为1001时，第22行以及第23行for循环最后一次进入循环体时，i的值为n-1，即1000。1000并不是a数组可以使用的下标。
如果运行该程序，会执行cin >> a[i]，i为1000，会发生数组越界，产生运行时错误。
因此该题叙述错误。
2. 输入的a[i]必须全为正整数，否则程序将陷入死循环。（ ）
答：F
根据上述分析，当a[i]为负数或0时，f(a[i])可以求出a[i]的补码中1的位数，g(a[i])可以求出a[i]最低位1的位权。并不会陷入死循环。
最简单的例子就是0，当a[i]为0时，f(a[i])第10行不会进入循环，会之间返回0。g(a[i])会返回0，不会陷入死循环。
因此该题叙述错误。
3. 当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。（ ）
答：F
首先输入的5是数的数量n，表示有5个数。而后向数组a输入5个元素2 11 9 16 10。

a[i]	a[i]的二进制补码	f(a[i])	g(a[i])	f(a[i])+g(a[i])
2	10	1	$(10{)}_2=2$	1+2=3
11	1011	3	$(1{)}_2=1$	3+1=4
9	1001	2	$(1{)}_2=1$	2+1=3
16	10000	1	$(10000{)}_2=16$	1+16=17
10	1010	2	$(10{)}_2=2$	2+2=4

输出应该为3 4 3 17 4，题目叙述中输出的最后一项为5，错误。

4. 当输入为 1 511998 时，输出为 18。（ ）
答：T
1个数，为511998。
将511998进行短除法（除基取余），将其转为二进制数，虽然有些繁琐，但也是可行的。
下面介绍相对简单的做法：观察可知511998=512000-2
512是2的幂，可以分别将512000与2转为二进制数，而后在二进制下相减，得到511998的二进制形式。
$512000=512\ast 1000=2^9\ast (8\ast 125)=2^9\ast 2^3\ast 125=2^{12}\ast 125$
$125=128-3=2^7-3=(10000000{)}_2-(11{)}_2=(1111101{)}_2$
该数再乘以$2^{12}$，就是将该数左移12位，得到$\mathrm{11111010...}(12位)...0$
再减去2，$2=(10{)}_2$，得到：$\mathrm{11111010...}(12位)...0-10=\mathrm{11111001...}(11位)...10$
记$n=511998$，那么$f[n]$为n在二进制下1的位数，有16个1，所以$f[n]=16$。
$g[n]$为最低位1与后面的0构成的数值，为$g[n]=(10{)}_2=2$
$f[n]+g[n]=16+2=18$，本题正确。

5. 将源代码中 g 函数的定义（14∼17 行）移到 main 函数的后面，程序可以正常编译运行。（ ）
答：F
函数必须先声明或定义后，才可以运行。如果将g函数移到主函数后，主函数内调用g函数时，g函数还没有声明或定义，因此会报错。
如果想将g函数移到主函数后，需要在主函数前加一句函数声明，才可以正常运行。
函数声明如下：

int g(int);

• 单选题:

6. 当输入为 2 -65536 2147483647 时，输出为（ ）。
A. 65532 33
B. 65552 32
C. 65535 34
D. 65554 33
答：B
两个数，第一个数为-65536。
根据常识应该知道，$-65536=-256\ast 256=-2^8\ast 2^8=-2^{16}$
a数组为int类型，是32位有符号整型。
$-65536$的原码为：$\mathrm{10...}(14位)...010...(16位)...0$
反码为：$\mathrm{1...}(15位)...101...(16位)...1$
补码为：$\mathrm{1...}(16位)...10...(16位)...0$
该数中1的位数有16个，最低位1与后面0构成的数值为$(\mathrm{10...}(16位)...0{)}_2=2^{16}=65536$
输出结果为$16+65536=65552$

第二个数为$2147483647$，该数为int类型可以达到的最大值，其补码为$\mathrm{01...}(31位)...1$ ，该数中1的位数有31个，最低位1与后面0构成的数值为1，输出结果为$31+1=32$
因此正确输出为$6555232$，选B

【答案】

1. F
2. F
3. F
4. T
5. F
6. B