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

1 个月前(已编辑)
/ ,
248
AI 生成的摘要
本文介绍了ICS课程中的第一个实验Data Lab,其目标是通过位运算和逻辑运算实现一系列函数,这些函数被视为谜题。这些谜题围绕位运算、补码运算和浮点运算展开。为完成实验,需要先解压并进入指定工作目录,采用Linux环境下的编译指令make编译代码。实验要求严格禁止使用循环、条件语句和宏等,并对操作符使用做了限制。通过btest、dlc、bdd checker和driver.pl等工具对代码进行测试和评分,同时提供了ishow和fshow工具辅助理解整数和浮点数的二进制表示。本文最后通过源码示例详细解释了部分谜题的解法和思路,包括位运算、补码运算和浮点数运算等,并展示了通过本地评分脚本获取的完整分数,实现了对所有谜题的解答。

Data lab 是 ICS 的第一个 lab,虽然说出来可能会很打击大家的积极性,但它确实也是 ICS 最简单的一个 lab。

在这个 lab 中,我们需要在各种限制下,基于位运算和逻辑运算,实现一些函数,这些函数也被称为谜题(puzzle)。

这些 puzzle 包括:

位运算:

名称描述评分最大操作次数
bitXnor (x)仅使用~和 | 来实现 (x ^ y)17
bitConditional (x, y, z)对每个比特分别执行 x ? y : z14
byteSwap (x, n, m)交换第 n 字节和第 m 字节216
logicalShift (x, n)向右逻辑移位 x,通过 n 位316
cleanConsecutive1 (x)清除 x 的二进制形式中连续的 1416
leftBitCount (x)计算 x 的二进制形式中前导的 1 的数量450

补码运算:

名称描述评分最大操作次数
counter1To5 (x, n)如果 x<5,返回 1+x,否则返回 1215
sameSign (x, y)如果 x 和 y 符号相同,返回 1,否则返回 025
satMul3 (x)将 x 乘以 3,如果溢出,上 / 下取到 325
isGreater (x, y)如果 x>y,返回 1,否则返回 0324
subOK (x, y)确定是否可以计算 x−y 而不溢出320
trueFiveEighths (x)将 x 乘以 5/8,避免溢出错误425

浮点运算:

名称描述评分最大操作次数
float_half (x)计算 x/2430
float_i2f (x)将整数 x 转换为浮点数430
float64_f2i (x)将双精度 x 转换为整数420
float_negpwr2 (x)计算 2 的 (-x) 次幂420

我们的所有代码编写,都是在 bits.c 中进行的。

写前须知

在一切开始之前,请记得先解压 datalab-handout.tar,并进入 datalab-handout 工作目录。

本 lab 要求在 Linux 环境下完成。Mac 和 Windows 均不适用,你可以考虑使用:

  • WSL2(Windows Subsystem for Linux 2):具体信息请自行搜索
  • Class Machine:由助教团队提供
  • 云服务器:如腾讯云、阿里云等

如果你的服务器是 64 位系统,那么你使用 make 编译的时候,可能会遇到如下错误:

这是因为你的系统缺少了 gcc-multilib,你可以通过如下命令安装:

代码风格

  • 不允许使用循环、条件语句(除非另有说明,如后续的浮点谜题)
  • 只有如下操作符可以使用:!~&^|+<<>>(除非另有说明)
  • 每个函数都存在一个最大操作次数的限制,大于或等于这个限制数,将会被扣分
  • 禁止使用宏,定义其他函数、调用其他函数
  • 禁止使用形式转换类型
  • 某些函数进一步限制了可以使用的操作符、常量和变量的数量
  • 函数变量一定要声明在函数顶部,不允许在函数中间声明变量

测评

btest:用于测试你的函数是否正确。仅在一个小的测试集上进行测试,不能完全保证你的函数是正确的。

注意,这里的 make 是必需的,每当你修改了 bits.c,都需要重新编译。有关编译的更多知识,你会在第七章学习到。

dlc:用于检查你的代码是否符合规范。

bdd checker:穷举测试所有可能的输入,完整地检查你的函数是否正确。

driver.pl:用于评分,检查你的函数是否符合规范且正确。

辅助工具

要使用辅助工具,你必须先编译:

ishow:用于显示整数的二进制形式。

fshow:用于显示浮点数的二进制形式。

bitXnor

  • 要求:仅使用 ~| 来实现 ~(x ^ y)
  • 允许的操作符:~|
  • 最大操作次数:7
  • 评分:1

利用离散数学中学过的德摩根律,我们可以对此式进行变换:

注:XNORXOR 运算的否定。

所以我们得到:

bitConditional

  • 要求:对每个比特(位)分别执行 x ? y : z
  • 允许的操作符:~&^|
  • 最大操作次数:4
  • 评分:1

我们利用 x 的每一位,来决定选择 y 还是 z 的一位(也即利用 & 的短路特性):

byteSwap

  • 要求:交换第 n 字节和第 m 字节
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:16
  • 评分:2

想要完成这个谜题,需要我们理解一个叫做 mask(掩码)的概念。

考虑如下真值表:

xyx & yx | y
0000
0101
1001
1111

我们可以发现,当 x 为 0 时,无论 y 为什么,x & y 都为 0;当 x 为 1 时,无论 y 为什么,x & y 都为 y

基于这个特性,我们可以构造一个 mask,以之对某个数进行 & 运算,从而实现将某些位清零,而保留其他位不变的目的。

考虑到 1 个字节有 8 位,我们可以构造 mask 如下,其实现了对于 x 只保留第 n 个字节,而将其他字节清零的目的:

我们继续利用这个特性,来实现 byteSwap

关于掩码的思想十分重要,我们不仅在后续的谜题中会用到,而且在后续的课程中接触各种各样的位向量时,也会用到。

logicalShift

  • 要求:把 x 逻辑右移 n
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:16
  • 评分:3

逻辑右移,即在右移的过程中,左边补 0。

直接使用 >> 运算符,会导致算术右移,即在右移的过程中,左边补符号位。

所以,我们需要一个 mask,其可以在逻辑右移后,对于负数(即最高位为 1)的情况,将算数右移导致的额外的前导 1 清零。

我们可以通过模拟 Tmin 算数右移 n 位的过程,从而获得这个掩码。

由于存在对于大常量的使用限制,这里使用 1 << 31 来构造 Tmin,即最高位为 1,其他位为 0 的数。

cleanConsecutive1

  • 要求:清除 x 的二进制形式中连续的 1
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:16
  • 评分:4

最容易想到的方法就是,通过将 x 分别左移、右移 1 位,获得两个 mask,再以这两个 mask 取或构造出一个新的、标志了连续 1 的 consecutive1_mask,对之取反,即得需要保留的位。最后将 x~consecutive1_mask 进行 | 运算,即可实现清除连续 1 的目的。

另外一种思路十分精巧,通过首先执行 int cur_and_right_mask = x & (x << 1),获得了一个当前位和右侧位都为 1 的掩码,随后执行 cur_and_right_mask | (cur_and_right_mask >> 1),实现了对于连续 1 的掩码。

为了更方便理解,举例如下(注意,i 从低位向高位增长,最低位为第 0 位,tcur_and_right_mask):

  1. = 1 当且仅当 = 1 且 = 1
  2. 所以 t 标记了 x 中,当前位和右侧位都为 1 的位
  3. 执行 (t | t >> 1),可以在 t 的基础上,将右侧位(即 )也标记为 1,也即额外标记了 x 中当前位和左侧位都为 1 的位
  4. 由于连续为 1 的位,要么是当前位和右侧位都为 1,要么是当前位和左侧位都为 1,所以执行 x & ~(t | t >> 1),可以将 x 中连续为 1 的位清零
  5. 额外利用 xt 的关系,4 中式子可以进一步化简为 x ^ (t | t >> 1),即 xt | t >> 1 的异或

关于 5,额外解释如下:

  1. = 0 时, = 0, = 0,所以 = 0, 异或 0,结果不变
  2. = 1 时,当且仅当 任一为 1 时, = 1, 异或 1,即将 置 0,此时即对应了连续为 1 的位

所以此题的解法如下:

leftBitCount

  • 要求:计算 x 的二进制形式中最高位开始的前导 1 的数量
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:50
  • 评分:4

这题的最大操作次数给的十分慷慨,但这并不代表这题很简单。

这题的主要思路是,利用任何一个数都能被唯一地表示为二进制,也即只能被唯一的拆分为 的形式,所以我们可以如下进行判断(伪代码):

接下来,我们需要思考如何使用位运算,实现判断 x 最高 16 位是否均为 1。

这等价于判断 ~x 最高 16 位是否均为 0。

基于此,我们设计实现思路如下:

其中,is_high_16_all_1 为 1,当且仅当 ~(x & (tmin >> 15)) 最高 16 位均为 0,也即 x 最高 16 位均为 1。

继续应用这个思路,我们就可以实现 leftBitCount(为了简便起见,各变量命名为 ):

counter1To5

  • 要求:如果 x<5,返回 1+x,否则返回 1
  • 允许的操作符:~&!|+<<>>
  • 最大操作次数:15
  • 评分:2
  • 题目保证:1 <= x <= 5

首先,我们思考一下如何判断 x 是否等于 5。

我们立刻想到,这可以通过异或运算来实现,即判断 x ^ 5 是否为 0。

然而不幸的是,这道题禁止使用 ^ 异或操作符。那么我们应该如何实现异或运算呢?

我们可以使用位级异或运算

这段代码的核心思想是,其返回的结果 res 的每一位 res_i 为 0,当且仅当:

  • x_i 为 0 的位上,y_i 也必然为 0,这样才能使 ~x_i & y_i 为 0
  • x_i 为 1 的位上,y_i 也必然为 1,这样才能使 x_i & ~y_i 为 0

这也就等价于,res_i 为 0,当且仅当 x_iy_i 相等。

这正是异或运算的定义。

结合这个思路,再额外注意到 1 的二进制形式为 0x00000001,-4 的二进制形式为 0xfffffffc(高 30 位均为 1,低 2 位均为 0),我们可以得到实现如下:

这里还有一个技巧就是,如何快速获得 -4 的二进制形式?

我们利用书上讲到的:对于非 Tmin 的补码,均有 -x = ~x + 1,所以我们令 x = 4,即得其二进制表示为 0...0100,对之取反,得 1...1011,再加 1,得 1...1100,即 -4 的二进制表示。

sameSign

  • 要求:如果 xy 符号相同,返回 1,否则返回 0
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:5
  • 评分:2

由于符号位都位于最高位,所以我们只需要对 xy 进行逻辑右移 31 位,再进行 ^ 异或运算,然后使用 ! 运算符,即可实现。

另外一种解法是首先使用 Tmin 作为掩码,取得 xy 各自的符号位:

缺点是会多使用一个操作符。

satMul3

  • 要求:将 x 乘以 3,如果溢出,上 / 下取到
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:25
  • 评分:3

首先,先思考怎么在位级运算中计算出 x * 3

很自然的想法是:

如果没有发生溢出,那么 xmul2mul3 的符号位应该均相。所以我们可以通过判断是否满足这个条件,来确定是否发生了溢出。

这里进行算数右移 31 位的原因是因为我们希望将 is_overflow 的每一位都搞成相同的 1(对应溢出的情况)或者相同的 0(对应未溢出的情况),从而使之可以作为一个掩码。

再考虑如何在溢出的情况下,根据 x 的符号位,返回

  • Tmin 的位级表示:10...0
  • Tmax 的位级表示:01...1

从而我们可以通过如下代码实现此功能:

最后,我们将这些思路整合起来,即可实现 satMul3

或者:

实测这里使用 btest 测试会出现错误结果,但是使用 bdd checker 测试却是正确的,原因不明。

isGreater

  • 要求:如果 x>y,返回 1,否则返回 0
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:24
  • 评分:3

首先,我们根据 xy 的符号位来分类:

xy 异号:那么显然只有 x 为正数,y 为负数的情况下,x>y 成立,这对应 x 的符号位为 0,y 的符号位为 1

xy 同号:此时我们不能直接判断 x - y 的符号位,因为如果 x = y 的话,x - y 的符号位为 0,但是 xy 显然不满足 x>y

我们又想到:

从而我们可以得到如下代码:

subOK

  • 要求:如果 x-y 不会溢出,返回 1,否则返回 0
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:20
  • 评分:3

因为 x = y + (x-y),所以 x - y 溢出等价于 y(x-y) 符号均与 x 符号不同。

(考虑课本图 2-26,大正数相加得负数,大负数相加得正数)

再结合有 -y = ~y + 1,我们可以得到如下代码:

所以我们可以通过如下代码实现:

特别地,由于 y = Tmin 的时候不满足 -y = ~y + 1,所以我们需要特别讨论一下:

如果 y = Tmin ,那么 (~y + 1) = y,所以原式等价于 !(((x ^ y) & (x ^ (x + y)) >> 31) & 1

x 为负数时(对应其最高位为 1),由于 y 的最高两位为 10,所以 x + y 的最高位必为 0,于是有原式等于 !((1 ^ 1) & (1 ^ 0)),也就是 1,这是正确的。

x 为正数时(对应其最高位为 0),由于 y 的最高两位为 10,所以 x + y 的最高位必为 1,于是有原式等于 !((0 ^ 1) & (0 ^ 1)),也就是 0,这也是正确的。

trueFiveEighths

  • 要求:计算 ,向 0 舍入
  • 允许的操作符:!~&^|+<<>>
  • 最大操作次数:25
  • 评分:4

5x 很好实现,只需要 x << 2 + x 即可。

y/8 也很好实现,只需要 y >> 3 即可,然而回忆书上讲到的,右移实现的是向下舍入而非向 0 舍入,我们必须对此进行修正。

书 P73 曾说到,对于这种情况,我们可以对于负数特判,加上一个偏移量(bias),其等于 ,其中 为右移的位数,然后再进行右移,就可以实现向 0 舍入。

基于此,我们可以得到如下代码:

float_half

  • 要求:计算浮点数 f 位级等效值,但是如果 f 是 NaN,直接返回 f
  • 参数和结果都作为无符号整数传递,但它们应被解释为单精度浮点值的位级表示
  • 允许的操作符:任何整数 / 无符号整数操作,包括 ||&&,同时允许条件语句和循环语句
  • 最大操作次数:30
  • 评分:4

首先,我们需要回顾一下 IEEE 754 单精度浮点数的表示方法,如下图所示(CS:APP 图 2-32):

IEEE-754

IEEE-754

对于单精度浮点数(float),有:

  • 符号位:1 位
  • 指数位:8 位,偏移量为 ,对于非规格化数,其指数位全为 0,指数为 ,对于规格化数,其指数位不全为 0,指数为 ,其中 为指数位的值
  • 尾数位:23 位,对于非规格化数,尾数为 ,对于规格化数,尾数为

对于双精度浮点数(double),有:

  • 符号位:1 位
  • 指数位:11 位,偏移量为 ,对于非规格化数,其指数位全为 0,指数为 ,对于规格化数,其指数位不全为 0,指数为 ,其中 为指数位的值
  • 尾数位:52 位,对于非规格化数,尾数为 ,对于规格化数,尾数为

复习完了,让我们重新回到题目。要计算 ,一个很朴素的想法就是直接对指数位进行减 1 操作即可。

然而,若以此法实现,我们还需要对以下几种情况进行特判:

  • f 为非规格化数时,其指数位全为 0,显然不能减 1,但此时我们只需要将尾数位右移 1 位即可
  • f 的指数位恰为 1 时,减 1 后会变成非规格化数,此时我们可以通过直接对指数位和尾数位整体进行右移 1 位的操作来弥补非规格化数的尾数位不加 1 的问题,然而同时带来了一个最低位是否要舍入的问题,需要我们进一步特判
  • f 为 NaN 时,我们需要直接返回 f

所以,我们可以得到如下代码:

(回忆一下,浮点数的舍入方式是,四舍六入五成双,也即当最低位为 0 时,直接舍去,当最低位为 1 时,且次低位也为 1 时,才会需要进位)

float_i2f

  • 要求:将整数 x 转换为浮点数
  • 参数和结果都作为无符号整数传递,但它们应被解释为单精度浮点值的位级表示
  • 允许的操作符:任何整数 / 无符号整数操作,包括 ||&&,同时允许条件语句和循环语句
  • 最大操作次数:30
  • 评分:4

我们知道,其实 intfloat 都是基于二进制的表示方法,这给于了我们基于位操作实现此函数的基础。

同时我们也知道,一个 int 有 32 位,其中有 31 位可以用以表示精度,而 float 的尾数位有 23 位,所以我们需要将 int 的精度位右移 8 位(即损失 8 位精度),从而得到 float 的尾数位。同时,我们还需要根据 “四舍六入五成双” 的原则,对于最低位是否要舍入进行判断。

于是,我们可以得到如下代码:

float64_f2i

  • 要求:将浮点数 f 转换为整数
  • 参数作为无符号整数传递,但它应被解释为双精度浮点值的位级表示,且第一个参数表示的是低 32 位,第二个参数表示的是高 32 位
  • 如果 f 不能用整数表示(例如超出表示范围、或者是 NaN),返回 0x80000000
  • 允许的操作符:任何整数 / 无符号整数操作,包括 ||&&,同时允许条件语句和循环语句
  • 最大操作次数:20
  • 评分:4

回忆之前提到的,对于双精度浮点数(double),有:

  • 符号位:1 位
  • 指数位:11 位,偏移量为 ,对于非规格化数,其指数位全为 0,指数为 ,对于规格化数,其指数位不全为 0,指数为 ,其中 为指数位的值
  • 尾数位:52 位,对于非规格化数,尾数为 ,对于规格化数,尾数为

从而我们知道,一个 double 有 52 位精度,而 int 只有 31 位精度,这不可避免的会导致精度损失。

同时,一个 int 最多只有 31 位精度,也代表了其表示范围不超过 -2^31 ~ 2^31-1,这是我们得以判断是否发生了溢出的基础。

我们还注意到,对于 double 中,指数位小于等于偏移量 1023 的数,其指数必为 2 的负幂次(特别地,对于 ±0,有除符号位外全为 0 的表示方式),这些数在转换为 int 时,必然会舍入到 0。

所以,我们可以得到如下代码:

float_negpwr2

  • 要求:计算 的浮点表示
  • 如果得到的结果太小以至于是一个非规格化数,返回 0;如果得到的结果太大以至于无法表示成浮点数,返回
  • 参数和结果都作为无符号整数传递,但它们应被解释为单精度浮点值的位级表示
  • 允许的操作符:任何整数 / 无符号整数操作,包括 ||&&,同时允许条件语句和循环语句
  • 最大操作次数:20
  • 评分:4

首先思考那些数可以被表示为浮点数。

我们知道,对于单精度浮点数(float),其指数位的偏移量为 ,指数位的范围为 ,对应的指数范围为 。其中,指数位为 0 的数为非规格化数,指数位为 255 的数为 NaN 或者 Inf,其他数为规格化数。

最小的非规格化数的位级表示为 0x00000001,对应的指数位为 0,尾数为 ,所以最小的非规格化数为

所以任何满足 ,也即 的数,都需要舍入为 0。

而最大的规格化数的位级表示为 0x7f7fffff,对应的指数为 254,尾数为 ,所以最大的规格化数为

再往上,就需要指数位全为 1,这时候就是 Inf 了。

也即,对于任何满足 ,也即 的数,都需要舍入为 Inf。

所以,我们可以得到如下代码:

本地评分

运行:

得到下列分数:

至此,我们就完成了 Data Lab 的所有题目,Congratulations!

参考资料

评论区加载中...