# Data Lab：位操作

原文：官方实验说明 (opens new window)
实验包：datalab-handout.tar

自学包说明：运行配置与原说明的差异

15-213，20xx 年秋季

布置日期：8 月 30 日；截止日期：9 月 12 日（星期三）晚上 11:59。

本次作业的主要负责人是 Harry Bovik（bovik@cs.cmu.edu）。

译注：20xx、SITE-SPECIFIC 段落及服务器变量均为原课程模板内容，按原文保留；日期和联系人也沿用原文。

# 1 引言

本次作业旨在让你更加熟悉整数和浮点数的位级表示。你将通过解决一系列编程“谜题”来达到这一目的。许多谜题带有很强的人为设计色彩，但在解题过程中，你会发现自己对位的思考深入了许多。

# 2 实验安排

这是一个独立完成的项目。所有作业均以电子方式提交。说明和更正将发布在课程网页上。

# 3 实验材料获取说明

SITE-SPECIFIC：在此插入一段文字，说明教师将如何向学生分发 datalab-handout.tar 文件。

首先，将 datalab-handout.tar 复制到 Linux 机器上你打算开展工作的一个（受保护的）目录中。然后执行命令：

unix> tar xvf datalab-handout.tar.

译注：上述命令末尾的句点见原 PDF，此处原样保留。

这将在该目录中解压出若干文件。你唯一需要修改并提交的文件是 bits.c。

bits.c 文件包含 13 道编程谜题各自的函数框架。你的任务是补全每个函数框架；对于整数谜题，只能使用直线式代码（即没有循环或条件语句），并且只能使用有限的几种 C 算术运算符和逻辑运算符。具体来说，只允许使用以下 8 个运算符：

! ~ &amp; ^ | + &lt;&lt; >>

少数函数还会进一步限制这一列表。此外，不允许使用超过 8 位的常量。详细规则及所要求的编码风格，请参见 bits.c 中的注释。

# 4 谜题

本节介绍你需要在 bits.c 中解决的谜题。

表 1 大致按照由易到难的顺序列出了这些谜题。“难度评分”一栏给出谜题的难度等级（即分值），“运算符上限”一栏给出实现每个函数时允许使用的运算符数量上限。有关函数应有行为的更多细节，请参见 bits.c 中的注释。你也可以参考 tests.c 中的测试函数。这些函数作为参考函数，用来表达你的函数应有的正确行为，但它们并不遵守对你的函数所规定的编码规则。

名称	描述	难度评分	运算符上限
`bitXor(x,y)`	仅使用 `&` 和 `~` 实现 `x \\|\\| y`。	1	14
`tmin()`	最小的二进制补码整数。	1	4
`isTmax(x)`	当且仅当 `x x` 是最大的二进制补码整数时为真。	1	10
`allOddBits(x)`	当且仅当 `x` 中所有奇数编号的位都为 1 时为真。	2	12
`negate(x)`	使用 `-` 运算符返回 `-x`。	2	5
`isAsciDigit(x)`	若 `0x30 ≤ x ≤`，则为真。	3	15
`conditional`	与 `x ? y : z` 相同。	3	16
`isLessOrEqual(x, y)`	若 `x ≤ y`，则为真；否则为假。	3	24
`logicalNeg(x))`	不使用 `!` 运算符计算 `!x`。	4	12
`howManyBits(x)`	用二进制补码表示 `x` 所需的最少位数。	4	90
`floatScale2(uf)`	对于浮点参数 `f`，返回 `2*f` 的等价位级表示。	4	30
`floatFloat2Int(uf)`	对于浮点参数 `f`，返回 `(int)f` 的等价位级表示。	4	30
`floatPower2(x)`	对于整数 `x`，返回 `2.0^x` 的等价位级表示。	4	30

表 1：Data Lab 谜题。对于浮点谜题，f 是与无符号整数 uf 具有相同位表示的浮点数。

译注：经核对原 PDF，表中确实写作 x || y、x x、isAsciDigit(x)、conditional、logicalNeg(x))；negate 的描述原文为 “Return -x with using - operator”，而 isAsciDigit 的不等式缺少上界。这里保留原文的笔误和缺漏，具体函数要求仍以原文所指的 bits.c 注释为准。

对于浮点谜题，你将实现一些常见的单精度浮点运算。在这些谜题中，允许使用标准控制结构（条件语句、循环），可以同时使用 int 和 unsigned 数据类型，包括任意无符号整数常量和整数常量。不允许使用任何联合、结构体或数组。最重要的是，不允许使用任何浮点数据类型、浮点运算或浮点常量。相反，任何浮点操作数都将以 unsigned 类型传入函数，任何返回的浮点值也都采用 unsigned 类型。你的代码应通过位操作来实现指定的浮点运算。

随附的 fshow 程序可帮助你理解浮点数的结构。要编译 fshow，请切换到实验材料目录并输入：

unix> make

你可以使用 fshow 查看任意位模式表示的是怎样一个浮点数：

unix> ./fshow 2080374784

Floating point value 2.658455992e+36
Bit Representation 0x7c000000, sign = 0, exponent = f8, fraction = 000000
Normalized. 1.0000000000 X 2^(121)

你也可以向 fshow 提供十六进制值和浮点值，它会解析出这些值的位结构。

# 5 评分

总分为 67 分，分配如下：

36 分：正确性。
26 分：性能。
5 分：风格。

正确性分。 你必须解决的谜题都被赋予了 1 至 4 的难度等级，其加权总分为 36。我们将使用下一节介绍的 btest 程序评估你的函数。如果一道谜题通过了 btest 执行的所有测试，你将获得该题的全部分数；否则不得分。

性能分。 在课程的这一阶段，我们最关心的是你能否得到正确答案。不过，我们也希望培养你尽可能保持代码简短、简单的意识。此外，有些谜题可以用蛮力方式解决，但我们希望你能更巧妙一些。因此，我们为每个函数规定了允许使用的运算符数量上限。这个限制非常宽松，目的只是排除效率极低的解法。每个正确且满足运算符数量限制的函数可得 2 分。

风格分。 最后，我们预留了 5 分，对你的解法风格和注释进行主观评价。你的解法应尽可能简洁、直观。注释应提供有用的信息，但不必写得很多。

# 自动评测你的作业

我们在实验材料目录中提供了一些自动评测工具：btest、dlc 和 driver.pl，帮助你检查作业的正确性。

btest： 此程序检查 bits.c 中各函数的功能正确性。要构建并使用它，请输入以下两条命令：
```
unix> make
unix> ./btest
```
注意，每次修改 bits.c 文件后，都必须重新构建 btest。

逐个实现函数，并在实现每个函数的过程中进行测试，会对你有所帮助。可以使用 -f 选项让 btest 只测试一个函数：
```
unix> ./btest -f bitXor
```
可以使用 -1、-2 和 -3 选项向它提供特定的函数参数：
```
unix> ./btest -f bitXor -1 4 -2 5
```
有关运行 btest 程序的说明，请查看 README 文件。
dlc： 这是 MIT CILK 小组的 ANSI C 编译器的一个修改版本，可以用来检查每道谜题是否遵守编码规则。典型用法是：
```
unix> ./dlc bits.c
```
除非发现问题，否则程序运行时不会输出任何信息。问题包括使用了不允许的运算符、运算符数量过多，或者整数谜题中出现了非直线式代码。使用 -e 选项运行：
```
unix> ./dlc -e bits.c
```
会让 dlc 打印每个函数使用的运算符数量。输入 ./dlc -help 可查看命令行选项列表。
driver.pl： 这是一个驱动程序，使用 btest 和 dlc 计算你的解答的正确性分和性能分。它不需要参数：
```
unix> ./driver.pl
```
教师将使用 driver.pl 评估你的解答。

# 6 提交说明

SITE-SPECIFIC：在此插入文字，告诉每位学生如何在贵校提交其解答文件 bits.c。

# 7 建议

不要在 bits.c 文件中包含 <stdio.h> 头文件，因为这会使 dlc 无法正确处理，并产生一些不直观的错误消息。即使不包含 <stdio.h> 头文件，你仍然可以在 bits.c 中使用 printf 进行调试；虽然 gcc 会打印一条警告，但可以忽略它。
dlc 程序对 C 声明形式的要求，比 C++ 或 gcc 的要求更加严格。具体而言，在一个块（用花括号括起来的内容）中，所有声明都必须出现在任何非声明语句之前。例如，它会对以下代码报错：
```
int foo(int x)
{
  int a = x;
  a *= 3;     /* Statement that is not a declaration */
  int b = a;  /* ERROR: Declaration not allowed here */
}
```

# 8 “击败教授”竞赛

为了增添趣味，我们提供一项自愿参加的“击败教授”（“Beat the Prof”）竞赛，让你与其他学生及教师比拼，为谜题编写效率最高的解法。目标是用尽可能少的运算符解决每一道 Data Lab 谜题。对于每道谜题，使用的运算符数量不超过教师所用数量的学生就是获胜者！

要提交参赛解答，请输入：

unix> ./driver.pl -u ‘‘Your Nickname’’

译注：命令中昵称两侧的成对弯引号按原 PDF 保留。

昵称长度限于 35 个字符，可以包含字母、数字、撇号、逗号、句点、连字符、下划线和 & 符号。你可以任意多次提交。你最近一次提交的结果会显示在实时排行榜上，仅以昵称标识。可以在浏览器中访问以下地址查看排行榜：

http://$SERVER_NAME:$REQUESTD_PORT

SITE-SPECIFIC：将 $SERVER_NAME 和 $REQUESTD_PORT 替换为你在 ./contest/Contest.pm 文件中设置的值。

← 实验资料 Bomb Lab：拆除二进制炸弹 →