课后作业
# 第三十四课
本次上传使用 cpp 文件上传，如无过程，上传 cpp 中使用注释阐明思路也可以，或者涉及哪些知识点，也可以写出来
# 阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√，错误填×)
# 程序一：
#include <stdio.h> // 引入标准输入输出库
int n; // 定义一个全局变量n，用来存储输入的整数个数
int a[1000]; // 定义一个大小为1000的整数数组a，用来存储输入的整数
// 函数f：计算整数x的二进制表示中有多少个1
int f(int x) {
int ret = 0; // 初始化返回值ret为0
// 当x不为0时，循环执行
for (; x; x &= x - 1) // 将x不断地与x-1进行按位与运算，直到x变为0
ret++; // 每执行一次循环，ret自增1，表示找到一个二进制中的1
return ret; // 返回ret，即x中二进制1的个数
}
// 函数g：返回整数x的最低位的1所表示的值
int g(int x) {
return x & -x; // x & -x 的结果是x的二进制表示中最低位的1所对应的值
}
int main() {
scanf("%d", &n); // 输入一个整数n，表示接下来要输入n个整数
// 循环输入n个整数，存储到数组a中
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
// 对数组a中的每个整数，计算f(a[i]) + g(a[i])的值并输出
for (int i = 0; i < n; i++)
printf("%d ", f(a[i]) + g(a[i]));
printf("\n"); // 输出一个换行符
return 0; // 返回0，表示程序正常结束
}
# 解析
- 综述
本题考察了位运算及进制转换相关的知识。
&表示按位与，即将参与运算的两个数转换为二进制后逐位进行与运算。只有当参与运算的对应两位均为1时，结果对应位才为1。
例如：
88 & 11 = (1000)_2 & (1011)_2 = (1000)_2 = 8
对于
f(x)函数f(x)的作用是计算x的二进制表示中有多少个1。
我们可以通过借位的思考来理解，借位本质上是将被借位的位置变为0，并将其右侧的0全部变为1。更具体地，可以将x写成(A)1(B)形式，其中B代表n个0，即A与B中间的1为x从右向左数第一个1。
因此，x-1将变为(A)0(C)形式，其中C代表n个1。根据按位与的定义，x & (x-1)将变为(A)0(B)。
本质上，x &= (x - 1)的作用是将x的最右侧的1变为0。每次循环将一个1变为0，循环终止条件是x变为0，因此ret实际上统计了x二进制表示中1的数量。对于
g(x)函数g(x)返回x & (-x)的值。负数在计算机中的表示为原正数二进制取反后加1。
例如，10的二进制表示为0000 1010，取反后为1111 0101。
1111 0101 + 1 = 1111 0110
即 -10 的二进制表示为 1111 0110。可以发现，+1 的操作导致了进位，进位将取反后的二进制数码中最右端的所有 1 变为 0，并将取反后二进制数码中从右边数第一个 0 变为 1。
因此，x & (-x) 将得到除了在原数中最右侧的 1 为 1，其余位置全为 0 的二进制数。
例如：
0100 0000 & [-(0100 0000)] = 0100 0000 & 1100 0000 = 0100 0000
实际上，由此可得当一个偶数与它的负值相与时，结果是能被这个偶数整除的最大的 2 的 n 次幂；当一个奇数与它的负值相与时，结果一定是 1。
判断题：
- 输入的
n等于1001时，程序不会发生下标越界。 （ x ）
a数组的大小为1000，因此下标为0~999，1001会越界。
- 输入的
- 输入的
a[i]必须全为正整数，否则程序将陷入死循环。 （ x ）
f(x)在x为正整数与负整数时均可正常运作，不会进入死循环。
- 输入的
- 当输入为“
5 2 11 9 16 10”时，输出为“3 4 3 17 5”。 （ x ）
- 最后输出为
f(a[i]) + g(a[i])形式。当输入5（二进制为101）时： - 1 的个数为 2 个，则
f(a[i]) = 2； - 最低位的
1表示为1，则g(a[i]) = 1； - 输出为
(2 + 1 = 3)。
以此类推……然而当输入为10（二进制为1010）时， f(a[i]) = 2，g(a[i]) = 2；- 输出为
(2 + 2 = 4)，不应该为5。
- 当输入为“
- 当输入为“
1 511998”时，输出为“18”。 （ √ ）
- 本题考察了进制转换。
511998的二进制表示为111 1100 1111 1111 1110，所以f(511998) = 16，g(511998) = 2，输出18，正确。
- 当输入为“
- 将
g函数移到main函数后，程序可正常编译运行。 （ x ）
- 若要将函数移动至
main函数后面，则需要先在main前进行声明，否则不能编译运行。
- 将
单选题：
- 输入为“
2 -65536 2147483647”时，输出为：B
- A.
65532 33 - B.
65552 32 - C.
65535 34 - D.
65554 33
- 输入为“
显然硬算相当容易出错，且时间成本很高。观察发现 2147483647 实际上就是 int 的最大值，即 2^{31}-1。故此 f(2147483647) = 31，g(2147483647) = 1，f(x) + g(x) = 32，因此第二个输出为 32，选 B。
# 程序二：
#include <stdio.h> // 引入标准输入输出库
#include <string.h> // 引入字符串处理库
char base[64]; // 用于存储Base64编码表
char table[256]; // 用于存储解码查找表
char str[256]; // 用于存储输入的字符串
char ans[256]; // 用于存储解码后的结果
// 初始化函数，用于生成Base64编码表和解码查找表
void init() {
// 填充base数组，前26个元素为大写字母A-Z
for (int i = 0; i < 26; i++) base[i] = 'A' + i;
// 接下来26个元素为小写字母a-z
for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
// 接下来10个元素为数字0-9
for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
// 最后两个元素为Base64特殊字符 '+' 和 '/'
base[62] = '+', base[63] = '/';
// 初始化table数组，所有元素设为0xff，表示无效字符
for (int i = 0; i < 256; i++) table[i] = 0xff;
// 将base数组中的字符映射到table数组中，索引为字符ASCII值，值为Base64索引
for (int i = 0; i < 64; i++) table[base[i]] = i;
// '=' 字符用作填充，在table中设置为0
table['='] = 0;
}
// 解码函数，将Base64编码的字符串解码为原始数据
void decode(char *str) {
char *ret = ans; // 解码后的结果存储在ans数组中
int i, len = strlen(str); // 获取输入字符串的长度
// 每次处理4个字符，解码为3个字节的数据
for (i = 0; i < len; i += 4) {
// 解码第一个字节，取第一个字符对应的索引左移2位，加上第二个字符右移4位的部分
(*ret++) = table[str[i]] << 2 | table[str[i + 1]] >> 4;
// 如果第三个字符不是'='，继续解码第二个字节
if (str[i + 2] != '=')
(*ret++) = (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
// 如果第四个字符不是'='，继续解码第三个字节
if (str[i + 3] != '=')
(*ret++) = table[str[i + 2]] << 6 | table[str[i + 3]];
}
}
// 主函数，程序入口
int main() {
init(); // 初始化编码和解码表
printf("%d\n", (int)table[0]); // 输出table数组中索引0的值，即'='的映射值，结果为0
scanf("%s", str); // 输入一个Base64编码的字符串
decode(str); // 对输入的字符串进行解码
printf("%s\n", ans); // 输出解码后的结果
return 0; // 程序正常结束
}
# 解析
综述 这是一道难题，需要一定的背景知识才能更好地理解。题目实际上是在解码用 Base64 加密的一串字符串。Base64 是一种将非 ASCII 字符的数据转换成 ASCII 字符的方法，特别适合在 HTTP、MIME 协议下快速传输数据。虽然也可以用于加密，但这种加密方法比较初级。
加密方式：
一个字符在计算机中对应的是 8 个 bit。
例如字符'a'在计算机中对应的 ASCII 码是 97，对应的二进制表示是0110 0001，占用 8 个 bit。
将三个字符对应的 24 个 bit 每 6 个一组，变成 4 个元素进行重新编码就达到了加密的目的。
因此，解码的过程就是将这四个元素还原成三个元素。init()函数初始化：base数组的下标 0~63 对应字符 ASCII 码中的A~Z、a~z、0~9、+和/。加密时通过base数组进行映射加密。table数组则使用A~Z、a~z、0~9、+和/作为下标，对应 0~63 的值，用于解码。字符'='对应值为 0，在本题中可以理解为占位符的作用。
decode()函数：
如上所述，解码方式是将每四个元素还原为三个元素。因此，循环变量i每次加 4，一次对四个元素进行解码处理。由于加密过程是将三个 8 bit 分为 4 份，每份 6 bit。
我们要还原第一个字符需要使用密码的第一个字符的全 6 bit 与第二个字符的前 2 bit。
同理，还原第二个字符需要密码的第二个字符的后 4 bit 与第三个字符的前 4 bit。
还原第三个字符则需要密码的第三个字符的后 2 bit 与第四个字符的全 6 bit。
接下来来看具体的位运算实现。
- 还原第一个字符：
table[str[i]] << 2 | table[str[i + 1]] >> 4
先用table将字符转回数码形式。由于我们需要密码第一个字符的全 6 bit 与第二个字符的前 2 bit，因此将第一个密码字符左移 2 位，相当于为第二个字符的前 2 bit 腾出空间。然后将第二个密码字符右移 4 位，得到第二个字符的前 2 bit 并置于一个数码的最右端。接着进行一次按位或运算，这 2 bit 就填入第一个字符预留的空间中形成 8 bit 数码，经过char类型强转即可解码为第一个字符。
第二个和第三个字符的还原方法相同。特别地，第二个字符的还原中出现了 table[str[i + 1]] & 0x0f。
0x0f 对应二进制的 00001111，与运算的意义是取最低的 4 位。
判断题：
- 输出的第二行一定由小写字母、大写字母、数字和“
+”、“/”、“=”构成的字符串。 （ x ）
- 错误，完全有可能出现其他字符。
- 输出的第二行一定由小写字母、大写字母、数字和“
- 可能存在输入不同，但输出的第二行相同的情况。 （ √ ）
- 正确。例如
'a0=='和'a1=='的解码结果均为'kk'。这是因为'='忽略了密码字符 0 和 1 在后四位上的不同，不将后 4 位加入解码。
- 输出的第一行为“
-1”。 （ √ ）
- 正确。
table初始化为0xff，同时table[0]并未在此之后被赋值。0xff的二进制表达为补码11111111，十进制表达即为-1。
- 输出的第一行为“
单选题：
- 设输入字符串长度为
n``，decode函数的时间复杂度为：
- A.
Θ(√n) - B.
Θ(n) - C.
Θ(n log n) - D.
Θ(n^2)
- 设输入字符串长度为
正确。观察 decode 函数中的循环，实际上遍历了整个传入数组，每个字符进行的操作是常数次，因此渐进时间复杂度为 O(n)。
- 输入为“
Y3Nx”时，输出的第二行为：
- A.
csp - B.
csq - C.
CSP - D.
Csp
- 输入为“
模拟程序操作：
t['Y'] | t['3'] = (24<<2 | 55>>4) = 01100011 = 99 = 'c't['N']<<6 | t['x'] = 01000000 | 00110001 = 113 = 'q'- 输入为“
Y2NmIDIwMjE=”时，输出的第二行为：
- A.
ccf2021 - B.
ccf2022 - C.
cff 2021 - D.
cff 2022
- 输入为“
由于最后有一个 '='，最后四个密码字符还原后为 2 个字符，因此一共应有 3+3+2=8 个字符，排除 A 和 B。模拟最后一个字符的还原发现还原后为 1，因此选择 C。