Writeup

datalab.pdf

15-213, Fall 20xx

Data Lab: Manipulating Bits

Harry Bovik ([e-mail]) 是本作业的负责人。

1. 介绍

本作业的目的是更加熟悉整数和浮点数的位级表示。你可以通过解决一系列的编程“谜题”来做到这一点。这些谜题很多都是人造的，但你会发现自己在处理这些谜题的过程中，会更多地考虑位。

2. 支持

这是一个个人项目。所有提交内容都是电子版。说明和更正将公布在课程网页上。

3. 讲义说明

SITE-SPECIFIC：此处插入一段内容，解释讲师如何给学生分发 datalab.handout.tar 文件。

开始先将 datalab-handout.tar 复制到一台 Linux 机器上（受保护的）目录中，您打算在该目录完成工作。然后输入命令

unix> tar xvf datalab-handout.tar

这会把许多文件解压到目录中。你唯一需要修改和提交的文件是 bits.c。

bits.c 文件包含了 13 个编程谜题的框架。你的任务是完成每个函数框架，对于整数谜题只能使用直线代码（即，没有循环或条件语句），以及有限数量的 C 语言算术和逻辑运算符，具体来说，你只能使用以下 8 个运算符：

! ˜ & ˆ | + << >>

一些函数进一步限制了这个列表。此外，不允许使用任何长度超过 8 位的常量。有关详细规则和代码样式要求的讨论，请参见 bits.c 中的注释。

4. 谜题

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

表 1 列出了从最简单到最困难的谜题。“难度级别”字段给出谜题的难度级别（点数），“最大操作符数”字段提供允许用于实现每个功能的最大运算符的数目。有关函数行为要求的更多详细信息，请参见 bits.c 中的注释。您也可以参考 tests.c 中的测试函数。这些函数被用作参考函数来表示函数的正确行为，尽管它们不满足函数的代码规则。

函数名	描述	难度级别	最大操作符数目
bitXor(x,y)	x 异或 y，只用 & 和 ~	1	14
tmin()	最小的整数补码	1	4
isTmax(x)	x 为最大的整数补码时为真	1	10
allOddBits(x)	x 的奇数位都为 1 时为真	2	12
negate(x)	使用 - 操作符返回 -x	2	5
isAsciDigit(x)	$\small 0x30\leqslant x \leqslant 0x39$ 时为真	3	15
conditional	等同于 x ? y : z	3	16
isLessOrEqual(x, y)	$\small x \leqslant 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 具有相同位表示的浮点数。

对于浮点谜题，你将实现一些常见的单精度浮点运算。对于这些谜题，您可以使用标准控制结构（条件语句、循环语句），并且可以同时使用 int 和 unsigned 数据类型，包括任意无符号和整数常量。不能使用任何联合体（union）、结构体（struct）或数组（array）。最重要的是，不能使用任何浮点数据类型、操作或常量。相反，任何浮点操作数都将作为无符号类型传递给函数，而返回的任何浮点值都将是无符号类型。你的代码应该执行位操作，以实现特定的浮点数运算。

提供的 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

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 混乱并导致一些非直观的错误消息。你仍然可以在 bits.c文 件中使用 printf 进行调试，而不用包含 <stdio.h> 头文件，尽管 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. “击败教授”比赛

为了好玩，我们提供了一个可选的“击败教授”比赛，让你与其他学生和讲师竞争，开发出最有效的谜题。目标是用最少的运算符来解决 Data Lab 的每个谜题。在每个谜题中，与讲师的操作符数目相匹配或击败的学生就是赢家！

要提交参赛作品，请键入：

unix> ./driver.pl -u "Your Nickname"

昵称限制为 35 个字符，可以包含字母数字、撇号（'）、逗号、句点、破折号、下划线和 &。你可以随时提交。你最近提交的内容将显示在实时记分板上，仅由你的昵称标识。您浏览下面网站查看记分板：

http://$SERVER_NAME:$REQUESTD_PORT

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