从零开始的Data Lab

[!CAUTION]

本笔记仅供参考，请勿抄袭。

声明

本笔记的写作初衷在于，笔者在做Data Lab的时候受到Arthals学长很大启发，同时25Fall的计算机系统导论课程改制增加了10分的Lab测试（虽然往年的期中期末中也会有一两道Lab相关选择题，但分值不大）。故将心路历程写成此笔记，以便复习，并供后续选课同学参考。

Data Lab简要介绍

Data Lab是《计算机系统导论》课程的第一个Lab，该课程使用流行的计算机基础教材《深入理解计算机系统》（又名CSAPP/没人理解计算机系统）。其Lab取材于美国卡耐基梅隆的同名课程，北京大学课程团队每年都会对Lab进行修改，导致每年的puzzle（下文会介绍）都不一样，这里仅给出思路的实现。

Data Lab对应的为教材第二章《信息的表示与处理》，主要考察对位运算的理解。在bits.c文件中，会给出16个对应的puzzle，其分值对应为1-4不等。每个puzzle会有操作符类型与操作符数量的限制，总分分为实现分与表现分，其中实现分即代码在对应操作符类型下能通过test即满分，若操作符数量超出限制即扣除一定比例表现分。总分原始分为80分，在测评后会乘1.25作为最终总分。在AutoLab上的提交次数最多不能超过16次。笔者的耗时大约在13-15小时左右。

这些puzzle包括：

位运算：

补码运算：

浮点数运算：

我们需要在文件bits.c中实现这些函数。

在动手之前

Linux相关

由于同学们可能是第一次接触Linux系统（事实上笔者也差不多），因此下面介绍Linux系统的相关知识。

值得庆贺的是，24秋往后的Lab完成均使用北大Linux俱乐部维护的CLab云服务器，使用专门为ICS提供的Ubuntu镜像，SSH配置也有助教指导，故忽略。

当然，如果有同学喜欢用虚拟机、双系统或者WSL完成，亦可。

下面介绍Linux系统的相关指令：

• 上传文件：scp [本地文件] ubuntu@[ip]"[文件夹]，亦可使用VsCode的Remote-SSH插件拖拽实现。
• 下载文件（到当前目录）：scp ubuntu@[ip]:/home/...
• 当前工作目录：pwd
• 当前文件夹列表：ls
• 进入xxx文件夹：cd xxx
• 返回上级文件夹：cd ..
• 创建文件夹：mkdir [name]
• 创建文件：touch [name]
• 删除：rm[option][name]
  • -r递归删除一个目录
  • -f强制删除
• 压缩与解压缩tar文件：tar [option][name] （常用：tar -xvf [name]）
  • -x 解压
  • -c 选择多个目录/文件进行打包
  • -f [PACAGE_NAME] 指定打包后文件名
  • -z 压缩与解压缩tar.gz文件
  • -C [TARGET_DIR] 指导解压目录
• 编译C文件：gcc [src] -o [dst]

函数要求

在bits.c的文件开头，有对函数编写的相关要求：

• 遵循C语言规范，先声明全部局部变量再写表达式，否则评测时会报错。
• 若超出函数的最大操作符数量限制，会被扣除表现分。
• 除非有特殊要求，否则不能使用条件语句与循环语句。
• 除非有特殊要求，否则不能使用宏、调用其他函数或声明其他函数。
• 除非有特殊要求，否则不能使用结构、联合等int类型外的数据类型。
• 除非有特殊要求，否则不能使用强制类型转换。
• 除非有特殊要求，否则只能使用!，~,|,&,+,^,<<,>>操作符，部分题目可能有更严格的要求。
• 除非有特殊要求，否则只能使用0~255之间的整数。

如何测评

在将bits.c文件提交到AutoLab前，可以使用压缩包内提供的测评工具进行本地测评。

每次修改你的bits.c文件，在进行测评前，都需要在终端内输入make命令进行编译。

btest：在一个小的数据集上进行测试，不检查函数规范以及函数要求，不保证测评正确。

1
2
3
4

./btest -f [func]
# 对函数[func]进行测试
./btest -f [func] -1 7 -2 0xF
# 对函数[func]进行测试，第一个参数为7，第二个参数为0xF

dlc：用于检查你的代码是否符合规范 ./dlc bits.c

bddcheck：在测试集上测试你的函数，检查是否能通过测试。

1
2
3
4

./bddcheck/check.pl -f [func]
# 对函数[func]进行完整测试
./bddcheck/check.pl 
# 对所有函数进行完整测试

drivsr.pl：对所有函数评分，运行上述三个测试器。

1

./driver.pl

一点提示

在动手之前，请牢记掩码、分治、溢出判断与浮点位表示的相关知识。

开始动手！

bitOr

• 要求：仅使用 ～ 和 & 来实现 x | y。
• 允许的操作符：~、&
• 最大操作次数：8
• 分值：1

Solution

在离散数学中，学习过以下知识

因此得到以下代码：

1
2
3

int bitOr(int x, int y) {
    return ~((~x) & (~y));
}

upperBits

• 要求：将32位二进制的高n位设置为1。
• 允许的操作符：!、~、&、^、|、+、<<、>>
• 最大操作次数：10
• 参数范围：[0,32]
• 分值：1

Solution

要将这个数的高位设置为1，自然会联想到用(1<<31)进行算术右移。
答案呼之欲出：

1
2
3

int upperBits(int n) {
    return (1 << 31) >> (n - 1);
}

然后，就会遇到尴尬的情况：当n=0时，无法使用条件分支判断其存在，必须另寻他路。
我们尝试着考虑左移，那么就必须构造-1，并除去0的情况。
这里介绍一个之后题目常用的技巧，用!!n将非零数字转化为1，零不变。
产生一个掩码mask，若n=0时其为0，反之为1。
然后取mask的相反数，左移(32-n)位，就能得到答案。

1
2
3
4

int upperBits(int n) {
    int mask = !!n;
    return (~mask + 1) << (33 + ~n);
}

fullAdd

• 要求：将x + y对16取模。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：30
• 参数范围：[0,15]
• 分值：2

Solution

这道题把+运算符给ban了，因此需要另寻他路。 首先，要有一个基本的认识，也就是异或运算在位级表示上，相当于不进位的加法。（想一想，是不是这样？）
因此，想要实现加法，也许我们只需要用异或实现，再把进位算出来？
基于这个猜测，马上着手验证，以模2加法为例。
取sum = x ^ y，则结果为sum & 1。
还是心存疑惑？接着用模4加法验证。
一个显然的事实是，模4加法必然是模2加法的推广，因此它的步骤有一部分与模2加法重合。
取sum_1 = x ^ y，进位标志为c_1 = (x & y) << 1。
此时取sum_2 = sum_1 ^ c_1，即若模2加法进位与异或为1同时成立，则结果为0（在低2位的意义下）；若其中有一个成立或均不成立，则结果正常。
最后，取结果为 sum_2 & 3。
相似地，对模任意二的次幂的加法，都可以采取相似的策略。
分治得到以下代码：

1
2
3
4
5
6
7

int fullAdd(int x, int y) {
    int sum_1 = x ^ y, c_1 = (x & y) << 1;
    int sum_2 = sum_1 ^ c_1, c_2 = (sum_1 & c_1) << 1;
    int sum_3 = sum_2 ^ c_2, c_3 = (sum_2 & c_2) << 1;
    int sum_4 = sum_3 ^ c_3;
    return sum_4 & 15;
}

rotateLeft

• 要求：将x的二进制表示循环左移n位。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：25
• 参数范围：[0,31]
• 分值：3

Solution

其实说白了，循环左移是无法直接实现的。
那么怎么办？铛铛，补码堂堂登场！
也就是，把循环左移后被拼到低位的位级表示取出来，再把另一部分取出来。
分别做相应处理后，拼到一起，就行了。
然后你可能会感到疑惑，取出原来的低位简单，由于整数运算是算术右移，而需要的是逻辑右移啊？
没关系，笔者从24秋的Data Lab中拷贝了逻辑右移的一份模板，可以直接使用（这个是24秋的puzzle）。

1
2
3
4
5

int logicalShift(int x, int n) {
    // 对Tmin（最高位为1）执行同样的右移操作，然后左移一位取反即得所需掩码
    int mask = ~(1 << 31 >> n << 1);
    return x >> n & mask;
}

于是，结合我们的上述分析，得到以下代码

1
2
3
4
5
6

int rotateLeft(int x, int n) {
    int temp = x << n;
    int mask = ~(1 << 31 >> (33 + ~n) << 1);
    int temp_2 = x >> (33 + ~n) & mask;
    return temp | temp_2;
}

bitParity

• 要求：判断x的二进制表示中是否有奇数个0，是则返回1，否则返回0。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：20
• 分值：4

Solution

要判断是否有奇数个0，换言之，即判断这个数是否有奇数个1（好一句废话）。
看到奇数个1，会想到什么？如果把它的位表示看成一个个0和1呢，有什么性质？
一个显然的事实是，把它们全部进行异或，由于异或运算满足交换律和结合律，最后得到的结果为1。
用相同的视角来看这道题，结合分治的思想，我们可以不断对x的位表示进行折叠和异或，从而通过最后的结果是否为1来判断。
于是得到以下代码：

1
2
3
4
5
6
7
8

int bitParity(int x) {
    x = x ^ (x >> 16);
    x = x ^ (x >> 8);
    x = x ^ (x >> 4);
    x = x ^ (x >> 2);
    x = x ^ (x >> 1);
    return x & 1;
}

palindrome

• 要求：判断x的二进制表示是否回文，是则返回1，否则返回0。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：40
• 分值：4
• 特殊要求：可使用大常数。

Solution

要判断二进制是否回文，要思考的是，回文有什么性质？
显然的就是它的定义，进一步推出，x的高16位的倒序与低16位相同。
于是就会想到，如何将x的高16位反转？
一个易见的事实是，如果我们把这16位编号为 $1 \sim 16$ ，则奇数编号的位数必然换到偶数编号的位数上。
并且，对于相邻两两组成一对的位数，它们最终的状态也是交换的。
推广到，4个/8个/16个一组的位数，它们最终的状态也是交换的。
由分治的思想，得到以下策略：
1.交换相邻两个位数的数码。
2.将相邻两个位数看成一块，交换相邻两个块的数码。
3.将相邻四个位数看成一块，交换相邻四个块的数码。
4.将相邻八个位数看成一块，交换相邻八个块的数码。
可以写出以下代码：

1
2
3
4
5
6
7
8
9

int palindrome(int x) {
    int temp_1 = (x >> 16);
    int temp_2 = x & 0x0000FFFF;
    temp_1 = ((temp_1 & 0x00005555) << 1) | ((temp_1 >> 1) & 0x00005555);
    temp_1 = ((temp_1 & 0x00003333) << 2) | ((temp_1 >> 2) & 0x00003333);
    temp_1 = ((temp_1 & 0x00000F0F) << 4) | ((temp_1 >> 4) & 0x00000F0F);
    temp_1 = ((temp_1 & 0x000000FF) << 8) | ((temp_1 >> 8) & 0x000000FF);
    return !(temp_1 ^ temp_2);
}

negate

• 要求：对x取相反数。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：5
• 分值：2

Solution

参见《深入理解计算机系统（第三版）》66页网络旁注，提到-x = ~x + 1。
于是得到以下代码：

1
2
3

int negate(int x) {
    return ~x + 1;
}

oneMoreThan

• 要求：判断y是否比x大1。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：15
• 分值：2

Solution

有了上一题的暗示，会想到直接计算y - x - 1 = y + ~x，然后与0异或，判断是否相等。
然后，就光荣地WA在./btest了，即对于样例x = TMAX，~x是TMIN，即x = TMAX, y=TMIN时返回1。
这时怎么办？当然是采用特判了！即如何合理转化if(x==TMAX) return 0
还记得上文提到的用!!n将非零数字转化为1，零不变这条结论吗，没错，可以写出以下代码。

1
2

int TMAX = ~(1 << 31);
int if_TMAX = !!(x ^ TMAX);

如果if_TMAX = 0，直接返回0，否则返回!((x+1)^y)。
于是得到以下代码：

1
2
3
4
5
6

int oneMoreThan(int x, int y) {
    /* 反例是TMIN,TMAX*/
    int tmax = ~(1 << 31);
    int if_overflow = !!(x ^ tmax);
    return (if_overflow & !((x + 1) ^ y));
}

ezThreeFourths

• 要求：将x * 3/4向零舍入。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：12
• 分值：3
• 特殊要求：考虑溢出情况。

Solution

参见《深入理解计算机系统（第三版）》第74页，练习题2.42，可以得到这道题的解法。
课本上的这道题介绍了如何在不使用三目运算符以及条件语句的情况下实现除2的次幂并向零舍入。
即巧妙地通过算术右移，判断出是否需要加上一个bias。
同时，对于题目中考虑溢出情况，不必做额外处理，因为int类型会自动计算溢出结果。
于是，得到以下代码：

1
2
3
4
5

int ezThreeFourths(int x) {
    int sum = (x << 1) + x;
    int bias = (sum >> 31) & 3;
    return (sum + bias) >> 2;
}

isLess

• 要求：判断x是否小于y，若是则返回1，否则返回0。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：24
• 分值：3

Solution

一个显然的思路是，取出y - (~x) + 1的符号位，但是会受到溢出的影响。
因此，需要通过分类讨论进行逐步排查。

• 若x, y异号，则x < y当且仅当x是负数，y是正数。
• 若x, y同号，则x < y转化为x - y + 1 <= 0，即x + ~y <=0，于是转化为x + ~y的符号位判断。

基于以上思路，得到以下代码：

1
2
3
4
5
6
7
8
9

int isLess(int x, int y) {
    int x_is_equal_to_y = x ^ y;
    int x_sign = (x >> 31) & 1, y_sign = (y >> 31) & 1;
    int sum = ((x + (~y)) >> 31) & 1;
    int is_not_same_sign = (x_sign ^ y_sign) & ((x_sign ^ 0) & (y_sign ^ 1));
    int is_the_same_sign = !(x_sign ^ y_sign);
    int res = (is_not_same_sign | (is_the_same_sign & sum)) & !!(x_is_equal_to_y);
    return res;
}

satMul2

• 要求：计算x * 2的结果，若正溢出则返回TMAX，若负溢出则返回TMIN。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：20
• 分值：3

Solution

相比24Fall的satMul3，这个puzzle相对简单一些，因为x与x的符号位必然相同，因此只需判断x与x+x的符号位是否相同就可判断是否溢出。
我们肯定要计算出x_sign与sum_sign以得出if_overflow，即是否溢出。
这题因为需要处理TMIN，因此把x_sign和if_oveflow计算为-1而非1，可以更好地发挥掩码的作用。
接着分类讨论，若if_overflow = 0，则返回sum。
若if_overflow = -1，若x_sign = -1，则返回TMIN；反之返回TMAX。
但是，需要通过一个通式实现上述分类讨论，怎么办？
一个显然的想法是，通过|运算符实现，当if_overflow = 0时，另一侧取0。反之亦然。
于是得到以下框架：return (~if_overflow & sum) | (if_overflow ?)
然后就是区分TMIN和TMAX，若x_sign = 0，取~x_sign = -1，此时与TMIN异或得TMAX。
若x_sign = -1，取~x_sign = 0，此时与TMIN异或得TMIN。
于是得到以下代码：

1
2
3
4
5
6
7

int satMul2(int x) {
    int sum = x + x;
    int if_overflow = (x ^ sum) >> 31;
    int t_min = 1 << 31;
    int x_sign = x >> 31;
    return (~if_overflow & sum) | (if_overflow & (~x_sign ^ t_min));
}

modThree

• 要求：计算x % 3的结果。
• 允许的操作符：!、~、&、^、|、<<、>>
• 最大操作次数：60
• 分值：4

Solution

本题可以说是25秋的最难puzzle。
首先，要计算x % 3的结果，因为是基于二进制来实现，必然要探索二进制表示与3的关系。
先将整数的二进制表示看作无符号整数的二进制表示，对于负数，可以通过判断其的符号位，然后再通过最高位的关系对余数作相应处理。
一个显然的事实是，二进制的偶数位表示，2 ^ n % 3 = 1，而对于奇数位，2 ^ n % 3 = -1。
于是，受到分治思想的启发，可以将所有的偶数位全部合并至第2位，将所有的奇数位全部合并至第1位，这样就能将余数限制在 $0 \sim 3$ 。
随后，通过判断x是否为3，将其转化为0，限制x为 $0 \sim 2$ 。
下面我们对负数进行处理，由于 $2^{31} - (-2^{31}) \equiv 1 (\mathrm{mod} \ 3)$ ，因此若为负数则需要减去1。
此时发现，如果原来计算出的x，如果它是负数，在进行负数处理之前，如果x是2，那么最终答案应该为-2而非1。
而如果，原来计算出的x，如果它是负数，并且x是0或1，那么进行负数处理后会变为-1和0，与预期条件相符。
于是，我们需要判断，若x是负数且x = 1，那么需要再对它减去3。
这段思路可能不是同学所有思路里最简洁的，但是笔者在这问上确实燃尽了，花的时间应该有3h左右。
基于以上思路，得到以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int modThree(int x) {
    int x_sign = (x >> 31) & 1;
    int tmin = 1 << 31;
    int mask_1 = 0xFF + (0xFF << 8);
    int mask_2 = ~(tmin >> 8 << 1);
    int mask_3 = ~(tmin >> 4 << 1);
    int mask_4 = ~(tmin >> 2 << 1);
    int is_3;
    int mask_sign;
    int x_1, x_2;
    int pd;
    x = (x >> 16 & mask_1) + (x & mask_1);
    x = (x >> 8 & mask_2) + (x & 0xFF);
    x = (x >> 4 & mask_3) + (x & 0xF);
    x = (x >> 2 & mask_4) + (x & 3);
    x = (x >> 2 & mask_4) + (x & 3);
    x = (x >> 2 & mask_4) + (x & 3);
    is_3 = !(x ^ 3);
    x = x + ((~3 + 1) & (~is_3 + 1));
    mask_sign = ~x_sign + 1;
    x_1 = x + mask_sign;
    pd = !(x_1 ^ 1) & x_sign;
    x_2 = x_1 + ((~3 + 1) & (~pd + 1));
    return x_2;
}

float_half

• 要求：计算0.5 * x的浮点表示，如果x = NaN，直接返回x。
• 允许的操作符：所有整型/无符号整型的操作符
• 最大操作次数：30
• 分值：4
• 特殊要求：本题可以使用条件和循环语句。
• 特殊要求：本题可以使用大整数。

Solution

接下来的四题浮点数运算与24秋的puzzle大差不差，笔者参考Arthals学长的博文写出代码。
首先，作为浮点数，一定要先取出它的符号位，指数位以及尾数位。
然后，如果x = NaN or inf，直接返回。
接着，一个显然的想法是，直接对指数位减1，就可以得到0.5 * x。
剩余的就是几种情况，如下：

• 若x是非规格化数，则它的指数位全为0，此时直接将尾数位右移即可（注意，由于IEEE表示的向偶数舍入机制，最后两位需要考虑都为1的情况）。
• 若x是规格化数，但其指数为1，则其右移后会变为非规格化数，此时其表示的指数不变，但是原先规格化数尾数位自带的1，变为指数位右移后得到的1/2，同时再考虑向偶数舍入的机制。
• 对于一般的规格化数，直接将其指数位减1即可。

基于以上思路，得到以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

unsigned float_half(unsigned uf) {
    int x_sign = uf & 0x80000000;                                                // 取符号位
    int e_mask = 0x7f800000;                                                     // 指数位掩码
    int x_e = uf & e_mask;                                                       // 取指数位
    int x_m = uf & 0x007fffff;                                                   // 取尾数位
    int if_double_one = !((uf & 3) ^ 3);                                         // 是否需要进位
    if (x_e == e_mask) return uf;                                                // 特殊情况直接返回
    if (!x_e) return x_sign | ((x_m >> 1) + if_double_one);                      // 非规格化数
    if ((x_e >> 23) == 1) return x_sign | (((x_e | x_m) >> 1) + if_double_one);  // 指数位为 1
    return x_sign | ((((x_e >> 23) - 1) << 23) & e_mask) | x_m;                  // 一般情况
}

float_i2f

• 要求：将整数x转换为浮点数
• 允许的操作符：所有整型/无符号整型的操作符
• 最大操作次数：30
• 分值：4
• 特殊要求：本题可以使用条件和循环语句。
• 特殊要求：本题可以使用大整数。

Solution

由于int类型的精度有31位，而float类型的精度只有23位，因此在转换时会有精度损失。
首先，尽可能把原数的前导零去掉，使得容易处理指数位。
同时，还需要将负数转换为正数，以便处理，最后只需要加上符号位即可。
此时，0和TMIN就会妨碍去除前导零和取补码，应当先特判。
随后，需要取出float类型的尾数位并去掉规格化数隐含的前导1，结合掩码实现。
接着，对被舍入的尾数判断是否需要进位，并判断加上进位后的尾数是否超过范围了，多余的移给指数位。
最后，将符号位、指数位和尾数位拼接起来。
基于上述思路，得到以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

unsigned float_i2f(int x) {
    unsigned x_sign = (x >> 31) & 1, x_e = 31, x_m, is_add, bias = 0x7F, ux_e, mask = 0x7FFFFF;
    if (x == 0) return 0;
    if (x == (1 << 31)) return 0xCF000000;
    if (x_sign) x = -x;
    // 找到最高有效位。
    while (!(x >> x_e)) x_e--;
    ux_e = x_e + bias;
    x = x << (31 - x_e);
    x_m = (x >> 8) & mask;
    is_add = x & 0xFF;
    // 按向偶数舍入规则决定是否进位。
    x_m += (is_add > 0x80) || ((is_add == 0x80) && (x_m & 1));
    if (x_m >> 23) {
        x_m = x_m & mask;
        ux_e++;
    }
    return (x_sign << 31) | (ux_e << 23) | x_m;
}

float64_f2i

• 要求：将双精度浮点数x转换为整数，若超出范围（包括NaN和inf）则返回0x80000000u。
• 允许的操作符：所有整型/无符号整型的操作符
• 最大操作次数：20
• 分值：4
• 特殊要求：本题可以使用条件和循环语句。
• 特殊要求：本题可以使用大整数。

Solution

有关浮点数的题目，先取出符号位、指数位与尾数位。
一个显然的事实是，若x的指数位没有达到bias，即 $2^{11-1}-1=1023$ ，则必然会被舍入为0。
考虑数值超过int表示范围的数，int表示范围为 $-2^{31} \sim 2^{31} - 1$ ，意味着只要指数位大于等于31即可返回0x80000000u（因为刚好TMIN也是这个数）。
由于double类型的精度有52位，而int类型的精度有31位，因此在转换时会有精度损失，即对于double类型的尾数，其低 $52 - 31 = 20$ 位不可能得到整数。
同时，因为非规格化数已经被我们排除在外，因此需要考虑规格化数自带的1，即前导1。
随后，便是乘上原double类的指数，同时注意用掩码消掉算术移位可能存在的1。
最后，对符号位进行判断。
基于以上思路，得到以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int float64_f2i(unsigned uf1, unsigned uf2) {
    unsigned x_sign = (uf2) >> 31;
    int x_exp = (((uf2) >> 20) & 0x7FF) - 1023;
    unsigned x_m;
    int res_mask;
    unsigned res;
    if (x_exp < 0)
        return 0;
    else if (x_exp >= 31)
        return 0x80000000u;
    x_m = ((uf2 & 0xFFFFF) << 11) | ((uf1 >> 21) & 0x7FF) |
          (0x80000000);  // 只能取uf1的高11位和uf2的低20位，后续位数乘上指数一定不得整数，我们把前导1放在最高位
    res_mask = ~(0x80000000 >> (31 - x_exp) << 1);  // 用于消除算术右移可能产生的1
    res = (x_m >> (31 - x_exp)) & res_mask;  // 乘上前面的指数，因为默认前导1放在最高位，并且消掉算术右移可能存在的1
    if (x_sign)
        return -res;
    else
        return res;
}

float_pwr2

• 要求：计算2.0 ^ x的浮点表示，若太小则返回0，若太大则返回+INF。
• 允许的操作符：所有整型/无符号整型的操作符
• 最大操作次数：30
• 分值：4
• 特殊要求：本题可以使用条件和循环语句。
• 特殊要求：本题可以使用大整数。

Solution

先声明，本题如果想卷排名，可以参考CS-icez学长的打表实现 将操作符数降到1。
当然笔者在写Data Lab的时候还是自己写了代码，因此这里不赘述打表实现。
通过分析，可以将x分类为以下情况：

• 当2.0 ^ x小于float类型的最小非规格化数时，即 $2^{1-\mathrm{bias}} \times 2^{-23} = 2^{-149}$ ，返回0。
• 当2.0 ^ x小于等于float类型的最大非规格化数时，即 $2^{1-\mathrm{bias}} \times (1 - 2^{-23}) < 2^{-126}$ ，返回1<<(x+149)，作为尾数位。
• 当2.0 ^ x大于等于float类型的最小规格化数，且小于等于float类型的最大规格化数时，即 $2^{2^{8}-2-\mathrm{bias}} = 2^{127}$ ，返回(x+127)<<23，作为指数位。
• 当2.0 ^ x大于float类型的最大规格化数时，即 $2^{2^{8}-2-\mathrm{bias}} = 2^{127}$ ，返回INF。

基于上述思路，得出以下代码：

1
2
3
4
5
6

unsigned float_pwr2(int x) {
    if (x < -149) return 0;                // 太小
    if (x < -126) return 1 << (x + 149);   // 非规格化数
    if (x <= 127) return (x + 127) << 23;  // 规格化数
    return 0x7f800000;                     // 太大
}

注：该代码无法通过本地./bddcheck/check.pl测试，但是在Autolab上满分，原因未知。

进行评测

运行make以及./driver.pl，得到以下结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops     Puzzle
1       1       0       2       4       bitOr
1       1       0       2       7       upperBits
2       2       0       2       11      fullAdd
3       3       0       2       12      rotateLeft
4       4       0       2       11      bitParity
4       4       0       2       24      palindrome
2       2       0       2       2       negate
2       2       0       2       9       oneMoreThan
3       3       0       2       6       ezThreeFourths
3       3       0       2       21      isLess
3       3       0       2       11      satMul2
4       4       0       2       58      modThree
4       4       0       2       23      float_half
4       4       0       2       28      float_i2f
4       4       0       2       20      float64_f2i
4       4       0       2       9       float_pwr2

Score = 80/80 [48/48 Corr + 32/32 Perf] (256 total operators)

于是，完成了ICS的第一个Lab，Congratulations!

参考文献

Arthals-更适合北大宝宝体质的Data Lab踩坑记