> For the complete documentation index, see [llms.txt](https://hansimov.gitbook.io/csapp/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hansimov.gitbook.io/csapp/labs/data-lab/writeup.md).

# Writeup

> datalab.pdf
>
> 15-213, Fall 20xx
>
> Data Lab: Manipulating Bits

Harry Bovik (<bovik@cs.cmu.edu>) 是本作业的负责人。

## 1. 介绍

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

## 2. 支持

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

## 3. 讲义说明

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

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

```c
unix> tar xvf datalab-handout.tar
```

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

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

```c
! ˜ & ˆ | + << >>
```

一些函数进一步限制了这个列表。此外，不允许使用任何长度超过 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，请切换到讲义目录并键入：

```c
unix> make
```

你可以使用 fshow 查看任意模式表示的浮点数：

```c
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  |

**正确性分数。**&#x4F60;必须解决的谜题的难度等级在 1 到 4 之间，因此它们的加权和总计为 36。我们将使用 btest 程序评估你的函数，这将在下一节中介绍。如果一个谜题通过了 btest 的所有测试，你将获得满分，否则就没分。

**性能分数。**&#x6211;们在这门课上主要关心的是你能得到正确的答案。然而，我们想给你灌输一种让事情尽可能简短和简单的感觉。此外，有些谜题可以用蛮力解决，但我们希望你更聪明。因此，对于每个函数，我们已经为每个函数设置了允许您使用的最大数量的运算符。这个限制是非常慷慨的，它的目的是为了抓住效率极低的解答。每个满足运算符数目限制的正确函数都将得到 2 分。

**风格分数。**&#x6700;后，我们保留了 5 分，用于主观评价你解答的风格和你的注释。你的解决方案应该尽可能简洁明了。你的注释应当提供有用信息，但不能太多。

### 给你的工作自动评分

我们在材料目录提供了一些自动评分工具——btest、dlc 和 driver.pl——帮助你检查工作的正确性。

**btest：**&#x6B64;程序检查 bits.c 中函数功能的正确性。要构建和使用它，请键入以下两个命令：

```c
unix> make
unix> ./btest
```

**注意，每次修改 bits.c 文件时都必须重新构建 btest。** 你会发现，一次一个地完成这些函数，并在执行过程中对每个函数进行测试是很有帮助的。可以使用 -f 标志指示 btest 只测试单个函数：

```c
unix> ./btest -f bitXor
```

可以使用选项标志 -1、-2 和 -3 向其提供特定的函数参数：

```c
unix> ./btest -f bitXor -1 4 -2 5
```

**dlc：**&#x8FD9;是一个来自 MIT CILK 小组的 ANSI C 编译器的修改版本，您可以使用它来检查每个谜题是否符合代码规则。典型用法是：

```c
unix> ./dlc bits.c
```

程序将静默运行，除非检测到问题，例如非法运算符、运算符过多或整数谜题中的非直线代码。使用 -e 参数运行：

```c
unix> ./dlc -e bits.c
```

会让 dlc 打印每个函数使用的运算符的数目。键入 **./dlc -help** 以获取命令行选项的列表。

**driver.pl：**&#x8FD9;是一个驱动程序，使用 btest 和 dlc 计算你解答的正确性和性能分数。它不需要任何参数：

```c
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 强制执行。特别是，任何声明都必须出现在块（用大括号括起来的内容）中的任何非声明语句之前。例如，以下代码它会报错：

  ```c
  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 的每个谜题。在每个谜题中，与讲师的操作符数目相匹配或击败的学生就是赢家！&#x20;

要提交参赛作品，请键入：&#x20;

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

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

**http\://$SERVER\_NAME:$REQUESTD\_PORT**

**SITE-SPECIFIC：将 $SERVER\_NAME 和 $REQUESTD\_PORT 替换成你在 ./contest/Contest.pm 文件中设置的值。**