Writeup

datalab.pdf
15-213, Fall 20xx
Data Lab: Manipulating Bits
Harry Bovik ([email protected]) 是本作业的负责人。

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)
0x30x0x39\small 0x30\leqslant x \leqslant 0x39
时为真
3
15
conditional
等同于 x ? y : z
3
16
isLessOrEqual(x, y)
xy\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 文件中设置的值。