实验 1. 数据的表示#

本次实验精选了一些有趣的代码，巩固此阶段学习的位运算（bitwise）和整数的表示（integer representation）。另外，实验也会补充一些开发工具的使用和调试练习，目的是为了便于大家更好地完成作业。

本阶段的话题是熟练掌握位运算、位掩码、以及涉及到的调试命令，并能够将无符号整数表示为二进制多项式，将有符号整数表示为二进制补码。以下一些问题，旨在验证你的理解并让你进一步思考这些概念：

  • 考虑将整数的大小四舍五入到 2 的幂（例如，3 舍入到 4、4 到 4、5 到 8，对于负数：-3 舍入到 -4、-4 到 -4，依此类推）。正数的位模式与舍入后的值的位模式有何不同？负整数的情况呢？

  • 假设一个位运算表达式，可以将 unsigned int 值的高 N 位清零。请问这个表达式如何用算术方法来计算？

  • 在 gdb 下运行的程序时，什么时候向程序提供命令行参数：启动 gdb 时，还是从 gdb 内部运行程序时？

  • CSAPP 第 2 章提供了许多优秀的练习题和答案，可以进一步练习！

学习目标#

  • 复习位（bit）、位运算（bitwise）、位掩码（bitmask）等概念

  • 阅读并分析涉及位和整型运算的代码

  • 进一步练习在 Linux 远程开发环境下编辑、编译、测试、调试的工作流程

初始代码#

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/labs/lab1 ~/cs102

任务 1：位运算#

本节提供了一些练习，可以让你更加熟悉位运算、位掩码和移位操作。关于位运算的一些细枝末节的内容，这里再次强调一下：

  • 位运算符和其他运算符的优先级可能很容易出错。在优先级不明确的地方建议始终使用括号，目的是为了确保运算符按期望的顺序执行。例如，由于优先级规则，1<<2 + 3<<4 意味着 1 << (2+3) << 4，写成 (1<<2) + (3<<4) 可确保顺序正确。

  • 在数字字面量后面加 U 使其变为 unsigned int。例如，1U 表示无符号整数 1。

  • 在数字字面量后面加 L 使其成为 long。这可以解决一个很常见问题！例如，如果你想要将一个长整型的第 32 个位设置成 1，其他位保持 0，则以下命令不起作用：

    long num = 1 << 32;

    这是因为 1 默认情况下是 signed int，因为它只有 32 个位，你不能将其移位 32。正确的做法应该是这样的：

    long num = 1L << 32;

进制转换#

以二进制形式表达任何大于 char 的类型都很麻烦，因此十六进制是一个重要的表示形式。 十六进制和二进制之间的映射非常简单，你应该不断练习，直到能够一眼看出两者之间的转换。

十进制和十六进制之间的转换不值得练习，在必须手动转换的情况下，这可能是一件苦差事。

练习：参考第一个示例，练习十六进制到二进制。这些值是 32 位无符号整数。

十六进制

二进制

0x1

00000000 00000000 00000000 00000001

0x1ff

0x800000

0xa017

练习：练习二进制到十六进制。这些值是 32 位无符号整数。

二进制

十六进制

11111111 11111111 11111111 11111111

0xffffffff

00000010 00000000 10000000 00000000

00000000 00000000 00011111 11100000

11111000 01111111 00000000 00000000

没有必要记住整个 ASCII 表，但了解几个关键字符的位置将会很有用。使用 man ascii 学习三个字符“0”，“A”，“a”的代码，并使用它们进行以下转换。

练习：练习 ASCII 到十六进制。这些值是字符类型。

ASCII

十六进制

'I'

0x49

'5'

'd'

你还应该了解各种独特的无符号和有符号值的位模式。

练习：每个常量的位模式是什么？

值

二进制

-1

INT_MAX

INT_MIN

UINT_MAX

转换工具#

一旦熟悉了手动位计算，最好再学习下如何使用 Unix/Linux 工具来辅助进行这些计算。用于转换的最佳工具是调试器 gdb。即使没有要调试的程序，你也可以将它用作转换器。

练习：gdb 打印命令 print（缩写为 p）默认为十进制格式。使用 p/format 来选择其他格式，例如 x 代表十六进制、t 代表二进制、c 代表字符。更多信息另请参阅 GDB 手册。

$ gdb
(gdb) p 68
$1 = 68
(gdb) p/x 68
$2 = 44
(gdb) p/c 68
$3 = 'D'
(gdb) p/t 68
$4 = 1000100
(gdb) p 45 << 1        注意：不仅仅是常量，表达式也可以打印
$5 = 90

位运算#

你应该了解 C 语言中所有六个位运算符的行为：& | ~ ^ << >>。

练习：通过评估以下表达式来测试你对位运算的理解。为了简便，这里仅使用 char 来演示，对于 int 等其他类型，位运算的逻辑是一致的。

表达式

值

unsigned char this, that, result;

this = 0xf0

11110000

that = 0x55

result = this & that

result = this | that

result = this ^ that

result = ~this

result = this >> 2

result = that << 1

位向量#

位向量是一个独立的布尔值集合，用一个无符号值表示。一个特定位表示一个特定成员，如果该位在位向量中打开，则该位向量集合包含该成员。更改特定位的值可以在位向量集合中添加或删除某个成员。对位向量进行操作时，你可以综合应用位掩码和位运算来隔离某些指定的位。

位运算常用于测试、设置和清除指定的位，并执行一些简单的设置操作。这些经典的位运算惯用法值得我们了解并掌握！

练习：你知道如何操作位向量吗？用下面的练习测试一下。假设 mine 和 yours 都是无符号整数。术语“低”和“高”，“最右”和“最左”，是指“较低有效位”和“较高有效位”。

任务

C 表达式

测试 mine 最低位是否打开（1 表示开，0 表示关）

(mine & 1) != 0

将 yours 最低位打开或置 1

将 yours 最低位关闭或置 0

切换 yours 最低位

将 mine 和 yours 作并集

将 mine 和 yours 作交集

将 mine 和 yours 作差集

位掩码#

当访问单个位时，使用掩码来隔离指定的位，例如，mine & 1 中的掩码 1 用于测试最低有效位。更改掩码可以更改操作的位，例如，mine & 2 中的掩码 2 用于测试第二个最低有效位。将其他位包含到掩码中可以影响整个位组，例如，mine ^= 0x7 可以切换三个最低位。

练习：假设 mine 是一个无符号整数，用作位向量。对于以下任务，写出 C 语言的表达式。

任务

C 表达式

测试 mine 最低 2 个位是否有打开的位

(mine & 0x3) != 0

测试 mine 最低 2 个位是否全部打开

将 mine 最低 8 个位打开

将 mine 的所有位关闭

常量掩码应始终以十六进制表示，小十进制整数常量（0，1，…）除外，这是为了增加代码的可读性。对于复杂的掩码，则建议通过构造来表达，而不是硬编码一个魔法数字。你应该练习如何构造复杂的掩码，并在合适的位置使用常量定义（#define <CONSTANT> <VALUE>）。

练习：给出一个 C 表达式来构造以下每个掩码（32 位无符号整数）。位置值从最低有效位（位置 0）开始计数。

任务

C 表达式

所有位打开

~0 or -1

位置 n 打开，其他位关闭

最低 n 个位打开，其他位关闭

最高位打开，其他位关闭

最高 n 个位打开，其他位关闭

其他#

最后介绍一些稍微花哨的位运算。这些表达式可能很难推理，但通过这些练习可以更好地让你理解位运算以及补码等概念。

表达式

结果

1 << x

\(2^x\)

~x + 1

x >> 31

x &= (x - 1)

(x ^ y) < 0

任务 2：圆整#

打开 round.c 文件，查看函数 is_power_of_2 和 round_up 的代码。

  • is_power_of_2 利用了 2 的幂的位模式的独特属性。还记得该属性是什么吗？该值与其前一个值（num - 1）之间的关系（就两个值共有的位而言）是什么？代码如何利用这两个属性来确定给定值是否为 2 的幂？

  • round_up 返回第一个参数圆整后的值，圆整算法是向上舍入到第二个参数最近的倍数。首先考虑一般情况，当倍数不是 2 的幂时，如何使用算术运算向上舍入到下一个倍数？现在考虑倍数为 2 的幂的特殊情况，如何利用位运算取代低效的乘法/除法？

    函数 round_up 的计算过程类似于 Excel 中的 CEILING 函数，参考：Round a number up to nearest multiple - exceljet.net。

这些函数表明，数字的表示只是一种位模式，了解不同表示形式的优势，可以更方便地选择算术运算或位运算，以提高计算效率。

任务 3：中点计算#

对于本练习，首先阅读 Google 研究员 Joshua Bloch 的有关整数溢出常见错误的博客。仅仅计算中点这么简单的任务也可能隐藏危险！

我们需要一个能够安全、正确地计算两个整数中点的函数。如果中点不是精确的整数值，不必在意结果如何舍入，只要返回相邻的数就好。

文件 mid.c 包含四种不同的计算公式，用于测试简单程序中计算中点的任务。

函数 midpoint_original 大部分情况下都能工作，但出现了 Bloch 文章中指出的错误。如果 x + y 之和溢出，则结果错误。例如，调用 midpoint_original(INT_MAX-2, INT_MAX) 应返回 INT_MAX-1，但实际上返回 -2。在最初的程序中，该函数是用于计算两个数组索引的中点，这也就解释了为什么这个错误能够潜伏这么长时间而没有被发现（一般的数组很少有这么大的维度）。

Bloch 的文章提出了一些计算中点的修复方案。首先，他提供了 midpoint_A，然后提供了 midpoint_B 作为更快的替代方案。思考下 midpoint_A 和 midpoint_B 是如何修复上述问题的。midpoint_A 做了什么来避免溢出？midpoint_B 又做了什么？

只要两个输入均为非负，midpoint_A 和 midpoint_B 都可以正常工作。这个约束实际上从未被声明过，它只是隐含在原代码的上下文中，即输入是数组索引。如果输入有一个或两个为负值，那将发生什么问题呢？我们来调查一下！

  • 在输入为负数时，midpoint_A 容易受到与原始值不同的溢出影响，本例是在减法过程中发生的。产生溢出时，相减的两个操作数必须满足什么条件？减法运算溢出的结果是什么？找出一个你认为可能导致 midpoint_A 失败的输入，然后通过编辑 mid.c 程序测试你的输入。

  • 在输入为负数时，midpoint_B 不太容易发生错误。为了暴露 midpoint_B 中的问题，我们可以尝试逆向思考。思考一下，可以发现 midpoint_B 中的表达式永远不会得出负数——为什么呢？根据这一发现，任何中点为负的输入都会在 midpoint_B 上失败。找出一个此类输入并判断将返回什么值？编辑 mid.c 程序测试你的输入。

    如果在右移之前将总和转换回带符号的值，则可以解决这个问题，但代价是其他情况又可能失败。编辑代码验证下这个解决思路。似乎我们没法做到两全！

计算中点的最终版本是 midpoint_C，这段钻石般的代码来自非凡的 Don Knuth，并真正地解决了所有溢出问题！该函数的工作原理乍一看并不明显，但通过仔细研究，你可以了解它们是如何组合在一起的。

  • 首先考虑数字的按位表示以及对应于数字的二进制多项式。例如，0000...01011（即十进制数字 11）可以写为 \(1 * 2^0 + 1 * 2^1 + 0 * 2^2 + 1 * 2^3 = 11\)。

  • 现在比较 x 和 y 中不同幂次的项。按位 & 找出两个输入相同幂的项，按位 ^ 找出不同幂的项。

  • 如何将上述两个结果结合起来，以便找出中点二进制多项式的项？

  • 代码中使用 + 连接，为什么必须使用 +？尝试替换为 |，测试运行并思考这两个运算符的区别。

任务 4：工作流练习#

现在轮到你自己编写一些位运算代码并练习使用 Unix/Linux 开发工具了！

程序 parity 输出其命令行参数的奇偶校验。如果值的位模式中存在奇数个 1，则该值为奇校验；否则，为偶校验。通过运行 samples/parity_soln 程序测试不同的参数，来确认你对奇偶校验的理解。

假设 parity.c 中的代码是你的同事编写的，他声称它是“完整的”，但在出门的路上，他们发现了一些未修复的错误。你的任务是使用 sanitycheck 和 gdb 调试器测试并调试该程序，使其真正的完整。

关于 GDB，CS107 GDB and Debugging 是一个很好的参考。

  • 使用 make 构建程序并尝试使用不同的值运行 ./parity 几次。呃哦！似乎它认为每个值都是奇校验！有没有测试出哪些值具有偶校验？​

  • 在调试器下运行 gdb parity。可以使用 list 命令打印出 GDB 正在检查的部分代码。使用 list compute_parity 打印 compute_parity 函数并记下更新循环内结果的行号。

  • 接下来，在该行上设置一个断点，以便在 GDB 中运行程序时，可以在执行该行之前暂停并等待进一步的指令。可以通过键入 break XXX 来添加断点，其中 XXX 是函数名称或行号。

  • 在 gdb 下运行程序，输入 run，然后输入命令行参数（用于检查的数字）。 GDB 将运行程序并在断点处暂停。请注意，断点所在的行并没有执行。当停在断点处时，打印 result 的值，可以使用 p result（命令 print 的缩写）进行打印。咦？result 似乎包含了一个垃圾值。它竟然从未初始化过！这合法吗？在 Java 等具有安全意识的语言中，编译器可能会防止这种情况发生。

  • 执行 make clean 并 make 检查下有没有构建警告，此处你应该看不到 gcc 的任何提醒。在运行时，该变量将使用其内存中剩余的任何垃圾值。这给了我们一个经验教训——在自由放任的 C 语言世界中，你需要提高自己的警惕性。

  • 修复该程序、构建并重新运行。参考作业 0 中 sanitycheck 的使用，确保你的代码可以通过所有的默认测试。

既然更正后的程序通过了 sanitycheck 检查，那么就可以结束了，对吧？没那么简单~请记住，sanitycheck 检查的是否彻底取决于其测试用例。默认的测试用例仅仅是一个开始；你可以使用 custom_tests 添加自己的测试，以便更全面地验证该程序。

  • 仔细阅读 sanitycheck 默认的检查结果。它包括多少个不同的测试用例？这些测试用例是什么？​

  • 使用 custom_tests 中的附加测试进一步检查该程序。可以发现其中一项测试由于超时而失败，但这并不是说该程序效率较低，而是发生了无限循环（死循环）。

  • 调试无限循环的最佳方法是在 GDB 下运行程序，一旦停止，使用 Control-C 停止程序。 GDB 将显示程序停止时正在执行的位置，可以方便地查看具体发生了什么。

  • 一起试一试：在 GDB 中以负参数运行 parity 程序并让它停止响应。输入 Control-C 中断程序，并使用 backtrace 命令查看程序正在执行的位置——此时将显示当前的调用栈，可以查看当前正在执行函数。

  • 在循环中步进执行 step 并收集信息，以便诊断循环未正确退出的原因。

  • 一旦你查出问题的原因，就可以编辑代码来修复它。重新构建并测试，直到所有的错误都被消除为止。