作业 1. 有趣的位#
本次作业要求你完成三个程序，每个程序探索位运算或数字操作的某个特定方面。需要你编写的代码很短，但这些代码片段却非常强大！
这次作业用于测试你对第一个话题的理解。通过以下几个方面的训练，培养你的技能：
利用远程 Linux 开发环境，编辑、编译、测试并调试 C 程序
使用 C 位运算符和算术运算符编写操作位和整数的代码
在整数表示的限制下编写代码
为了帮助你评估学习进度，对于每个作业/实验，我们罗列了一些要点，并提供了一些思考问题。在完成作业后，可以使用这些问题进行自我检查。如果你不能很好地回答这些问题，那么还需要进一步努力。
绝对值是 2 的幂的所有负整数（-8、-32 等）的位模式有什么共同点？
如何确定整数位模式是否具有一对连续的“on”位？（使用循环将很简单，但也有一个巧妙的单一表达式……）
斯坦福大学计算机科学博士 Sean Anderson 有一个位魔法宝库 Bit Twiddling Hacks，推荐收藏。
初始项目#
你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：
cp -r /home/cs102-shared/assignments/assign1 ~/cs102
阅读并注释#
作业初始代码作为一个起点，你的首要任务应该是仔细阅读它。你要先弄清楚代码是如何运行的，以及它已经处理了哪些任务。基于这些代码框架，你可以规划如何开发自己的程序。每个程序大约有 25 行，需要你添加的代码可能只有十几行，因此需要你阅读的初始代码比你添加的新代码要多得多。
为了帮助你更好地上手作业任务开发，我们为每个程序提供了一些现成的代码，有些用于处理命令行参数，有些用于处理程序调用时的用户错误，还有一些比较重要的细节，特别是将字符串参数转换为数字。
作业 0 中的 triangle 程序使用了 atoi 函数，该函数使用起来相对简单一些，但却无法检测格式错误的输入。对于本次作业的这些程序，我们使用更强大但却更复杂的 strtol 函数。阅读 man strtol 中的函数文档并查看该函数在 convert_arg 中的使用方式。
下面一些问题可以用于自测：
在缺少参数的情况下调用
samples中的示例程序，程序将如何响应？如果参数过多又将如何？如何使用
error函数？将用户的字符串参数转换为数字时，传递给
strtol的基数是什么？这允许用户指定哪些基数的参数？另外，如何根据用户参数确定基数？如果
strtol在要转换的字符串中遇到无效字符，它会做什么？strtol的第二个参数如何用于错误检测？为什么end变量不用初始化也可以使用呢？如果不希望进行错误检测，你会传递什么作为第二个参数？如果要求转换的值太大而无法用
long表示，strtol会做什么？
阅读完代码后，尝试进行一些实验！构建并运行程序，使用不同的参数调用它们，看看每个程序是如何处理的。也可以在调试器下运行程序，逐步执行每行代码，并随时打印中间值。通过观察代码的运行情况，可以更好地理解代码。如果你能很好地回答上述自测问题，那么对初始代码的理解就够了，开始接下来的任务吧。
其他建议#
为了帮助你完成这次作业，我们整理了一些技巧，可以帮助你解决很多问题以及一些常见的位运算。
拥抱十六进制。十六进制可以非常方便地与二进制进行转换。每个字节都用两个十六进制数字表示，一个表示 4 个高位，另一个表示 4 个低位。十六进制掩码或通过其构造的掩码，可以更好地映射到二进制表示形式，并减少编码错误。例如，从 32 位值中提取符号位的掩码可以清晰地表示为 1 << 31 或 0x80000000，并且两者的可读性都非常好。该掩码也恰好是十进制的 2147483648U，但谁能一眼看出来呢？如果不小心输错了，比如 2147486348U，你能注意到吗？所以，不要使用十进制，优选十六进制！
学习位运算。调用 pow 函数来计算 2 的整数幂是一种浪费。使用 1 << 10 可以完美地计算 pow(2, 10)，并且需要更少的计算周期。位运算也是重排/隔离/更改位的正确工具，而不是间接地使用包含 2 的幂的整数乘法/除法/取模。
力求直接明了。可能有更直接的方法来编写某些位运算。以下是一些示例：
不要左移右移。在下面的代码中，第一个版本先右移然后立即左移，这个操作似乎只是将位模式循环回到原来的位置，但实际上右移将丢弃 lsb，然后左移将填零。这是擦除 lsb 的迂回方法，而更好的方法是直接将其屏蔽，如第二个版本所示：
result = (val >> 1) << 1; // original version
// Better version:
result = val & ~1; // better: directly turn off lsb
不要有多余/不必要的操作。想象一下，你的目标是提取一个字节的 4 个高位，并将它们下移到低半字节。你可以通过两个步骤（掩码和移位）来完成此操作，但实际上，移位已经丢弃低位了，因此无需掩码操作！
result = (val & 0xf0) >> 4; // mask off lower 4, then shift down
result = val >> 4; // better: directly shift,
// low-order bits gone!
不要掉进复杂的陷阱。当构造组合的位运算时，先考虑是否有更直接的方法来完成同样的事情，例如：
b = a | 0 // this is no op!
b = a ^ -1 // more clearly written as b = ~a
b = ~a + 1 // more clearly written as b = -a
b = (1U << 31) - 1 // INT_MAX from <limits.h>
b = INT_MIN >> 31 // This is -1!
起初，你可能会发现需要使用更长的表达式，但是仔细思考，你会发现还有更简洁的写法。最终的目标是避免将问题复杂化。
任务 1：饱和计算#
程序 sat 执行合成的饱和加法运算，饱和加法将结果限制在可表示的范围内。与补码加法“超范围即溢出”的行为不同，饱和加法在出现正溢出时返回该类型的最大值，在出现负溢出时返回最小值。饱和计算函数在图形学和数字信号处理应用中非常常见。
以下是 sat 程序的两个示例。第一个示例打印出 8 位有符号整数的取值范围是 \([-128, 127]\)。第二个示例尝试将 126 加到 5，结果会溢出并保持在最大值 127。
$ ./sat 8
8-bit signed integer range
min: -128 0xffffffffffffff80
max: 127 0x000000000000007f
$ ./sat 8 126 5
126 + 5 = 127
你的任务是编写以下函数，来实现 sat 程序的饱和加法。
long signed_min(int bitwidth);
long signed_max(int bitwidth);
long sat_add(long operand1, long operand2, int bitwidth);
参数 bitwidth 是 4 到 64 之间的数字。以位宽 bitwidth 表示的二进制补码有符号整数将被限制在固定范围内。函数 signed_min 和 signed_max 返回该范围的最小值和最大值。函数 sat_add 实现饱和加法运算，如果结果在范围内，则返回其操作数的总和；如果结果溢出，则根据情况返回最小/最大值。虽然此处两个操作数的类型为 long，但你可以假设操作数的值始终位于位宽 bitwidth 表示的有符号整数的范围内。话虽如此，但这么处理也意味着以位宽 bitwidth 表示的值的位数，实际上可能多于所需的位数。所以，这些额外的位需要进行合适的处理，以确保该值在 long 范围内能够进行正确的计算。
在编写 sat.c 的代码时，有三个重要的限制需要注意：
不可以使用关系运算符或
math.h中的函数。禁止使用关系运算符意味着，你的代码不可以出现< > <= >=这些比较操作，但你可以使用!= ==进行相等性检查。你也不应该调用math.h库中的任何函数，例如pow、exp2等。这些限制旨在引导你使用纯粹的位运算来实现代码。对于其他运算符，例如算术运算符、逻辑运算符、按位运算符……这里不作限制。参数
bitwidth没有特殊情况。无论位宽bitwidth的值是 4、64 还是介于两者之间的任何值，你的函数都必须使用一个统一的代码来处理。不可以对某些位宽的值进行特殊处理，比如使用if switch ?:根据位宽的值将代码分为不同的情况。但是，这并不意味着不能使用条件逻辑，例如单独处理溢出或非溢出的情况。不要使用循环或递归。此程序根本不需要循环或递归。
违反以上任何一个限制的代码都是不合格的，因此，请仔细检查你的实现是否合规！
任务 2：细胞自动机#
细胞自动机用于模拟细胞群落的生命周期，你可以将其视为一维细胞阵列，每个细胞可以是活的（live）也可以是死的（empty）。从初始模式开始，自动机使用一组简单的规则模拟后代细胞的出生和死亡。在这部分作业中，你将使用位和位运算实现细胞自动机，以便尽可能有效地利用内存。
这里将细胞群表示为一个 64 位无符号长整型数，每个位用于表示一维世界中的一个细胞。 1 表示单元格处于 live 状态，0 表示单元格处于 empty 状态。一个位的邻居是其紧邻的左右两侧单元格。规则集（ruleset）根据当前细胞及其邻居的状态，计算出该细胞在下一代中是活的还是死的。基于这种位向量的表示，读取和更新单个位可以使用位运算来完成。
Daniel Shiffman 的精美著作《代码的本质》对模拟的工作原理进行了精彩的解释。感兴趣可以阅读 Chapter 7. Cellular Automata 以获取更多背景信息。请注意，这里将使用比这些例子更复杂的细胞群落，但想法是一样的。阅读这些背景信息后，请继续阅读以下文字，以确认你对模拟过程的理解。（注意，上述链接的第 7.3 节也实现了一个自动机程序，但它采用了更重量级的数组/OO 设计。这里采用更简化的位运算来实现。）
如何从当前一代生成下一代？正如上述章节中提到的，一个单元格及其两个邻居形成了一个“邻域”。一个邻域实际上是 3 个位组成的数字，值的范围从 0 到 7。考虑一个活的单元，其左邻居是活的而右邻居是死的，二进制邻域表示为 110，即 3 个位表示的数字 6。那么该单元的下一代是活的还是死的，由规则集位置 6 的配置决定。规则集是一个 8 位的数字，每个位表示一个邻域的配置。假设规则集是 77，用二进制表示为 01001101。以最低有效位表示位置 0，则位置 6 的配置是 1，也就是说，这个单元的下一代是活的。
程序 automata 演示了一个基本的细胞自动机，根据指定的规则集，从初始状态开始进行多次迭代。如果下一代的状态不再改变，迭代就会提前终止。在下述输出中，每行代表一代，从顶部的第一代到底部的最后一代。下面显示了规则集 77 的程序运行示例：
$ ./automata 77
+
++++++++++++++++++++++++++++++ + +++++++++++++++++++++++++++++++
+ + + + +
+ ++++++++++++++++++++++++++ + + + +++++++++++++++++++++++++++ +
+ + + + + + + + +
+ + ++++++++++++++++++++++ + + + + + +++++++++++++++++++++++ + +
+ + + + + + + + + + + + +
+ + + ++++++++++++++++++ + + + + + + + +++++++++++++++++++ + + +
+ + + + + + + + + + + + + + + + +
+ + + + ++++++++++++++ + + + + + + + + + +++++++++++++++ + + + +
+ + + + + + + + + + + + + + + + + + + + +
+ + + + + ++++++++++ + + + + + + + + + + + +++++++++++ + + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + + + ++++++ + + + + + + + + + + + + + +++++++ + + + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + + + + ++ + + + + + + + + + + + + + + + +++ + + + + + + +
+ + + + + + + ++ + + + + + + + + + + + + + + + + + + + + + + + +
很酷吧？由于规则集是一个 8 位数字，这意味着细胞的演化将有 256 个不同的可能。可以尝试探索一些不同的值，看看有哪些非常酷的输出结果！
你的任务是为程序 automata 实现这些函数：
void draw_generation(unsigned long gen);
unsigned long advance(unsigned long gen, unsigned char ruleset);
函数 draw_generation 输出一个 64 字符组成的行，一个字符表示一个单元格。活细胞显示为 +（或者改为预定义的常量，参见作业代码），死细胞显示为空白。每一代的状态都是排好序的，与最高有效位（MSB）对应的单元位于最左列，而最低有效位（LSB）位于最右列中。建议优先实现这个函数。完成后，如果你运行该程序，它应该为第一代打印出一行，为下一代打印一个空行（这是由下面的 advance 函数初始代码返回的内容），接着它将停止迭代，因为后续状态没有改变。
函数 advance 会执行一次迭代，从当前一代生成下一代。对于每个细胞，该函数检查其邻域并根据规则集来确定下一代细胞的状态。外侧边缘的两个单元，由于只有一个邻居，需要特殊处理；不存在的邻居应该被视为死亡状态。
建议使用 sanitycheck 比较你的输出与示例程序的输出，而不是手动检查。为了便于识别，sanitycheck 会将活细胞显示为 *，将空细胞显示为 .。测试程序时，尝试使用不同的规则集。
你能找到产生谢尔宾斯基三角形的规则集吗？倒置的谢尔宾斯基三角形的规则集是什么？你最喜欢哪个规则集产生的输出？将这些规则集补充到 custom_tests，完善测试用例。
任务 3：UTF-8#
C 中的 char 是一种单字节数据类型，能够存储 \(2^8\) 种不同的位模式。 ASCII 编码标准 (man ascii) 为这些模式建立了到各种字母、数字和标点符号的映射，但仅限于 256 个选项，因此仅包含一个子集。 Unicode 是类似 ASCII 的更国际化的编码标准，它定义了一个通用字符集，支持现代和古代多种世界语言的字形（中文，埃及象形文字，原始表情符号等）。然而，如此大量的字符需要一个与单个字符不同的编码系统。对于这部分作业，你将实现最流行的 Unicode 编码 UTF-8，根据最近的统计，超过 98% 的网站（具有已知的字符编码）都使用该编码！
Unicode 将每个字符映射到一个码点（code point），该码点是一个十六进制数字。Unicode 标准中有超过 100 万个不同的码点！字符的码点通常以 U+NNNN 格式编写，表示十六进制值 0xNNNN。
然而，Unicode 标准没有指定如何以二进制形式最高效地编码这些码点。如何实际存储给定的码点，有多种可能的 Unicode 编码方式。为什么要存在多种编码方式？可能是有不同的优先级，也可能为了与其他非 Unicode 编码兼容，还有其预期的语言环境，空间效率等。根据编码方式的不同，一些问题可能有不同的答案：较小的码点是否应该与较大的码点占用相同的空间量？如果不是，我们如何确定编码的长度？是否可以保持与其他编码（例如 ASCII）的兼容性？
最流行的 Unicode 编码之一是 UTF-8。 UTF-8 之所以流行，部分原因是它保留了与 ASCII 的向后兼容性——事实上，它的设计使 ASCII 成为了 UTF-8 的子集，这意味着 ASCII 编码中表示的字符在 ASCII 和 UTF-8 中具有相同的编码。
UTF-8 编码使用 1 到 4 个字节表示一个码点，具体取决于码点的大小。如果它处在 U+0000 到 U+007F 范围内，则其 UTF-8 编码长度为 1 个字节。如果它处在 U+0080 到 U+07FF 范围内，则其 UTF-8 编码长度为 2 个字节。如果它处在 U+0800 到 U+FFFF 范围内，则其 UTF-8 编码长度为 3 个字节。最后还有一个 4 字节范围，但在本次作业中我们将忽略它。
UTF-8 的工作方式是将码点的二进制表示形式拆分到用于编码的字节中。
从
U+0000到U+007F的码点最多使用 7 位（这些称为“有效位”），编码使用 1 个字节其最高有效位为 0，其余位作为 7 个码点有效位。
从
U+0080到U+07FF的码点最多有 11 个有效位，编码使用 2 个字节第一个字节前缀是
110，后面跟着 5 个最高码点有效位；第二个字节前缀是10，后面是其余 6 个码点有效位。从
U+0800到U+FFFF的码点最多有 16 个有效位，编码使用 3 个字节第一个字节前缀是
1110，后面跟着 4 个最高码点有效位；第二个字节前缀是10，后面跟着 6 个最高码点有效位；第三个字节前缀是10，后面是最后 6 个码点有效位。
下面的表格总结了上面的设计规范。对于每个字节的布局，所有表示形式的 0 和 1 位都是固定的。xxx 位存储码点的二进制表示形式。
Code Point Range |
Significant Bits |
UTF-8 Encoded Bytes (Binary) |
|---|---|---|
|
7 |
|
|
11 |
|
|
16 |
|
如你所见，单字节序列存储码点的 7 位，双字节序列存储 11 位（第一个字节 5 位，另一个字节 6 位），三字节序列存储 16 位（分别存储 4 位、6 位和 6 位）。UTF-8 字节长度取决于存储码点的所有位需要多少字节（1 表示最多 7 个有效位，2 表示最多 11 个有效位，3 表示最多 16 个有效位）。
在单字节序列中，高位始终为 0，其他 7 位是码点本身的值。因此，前 128 个 Unicode 码点与 ASCII 字符使用相同的二进制表示！
对于多字节序列，第一个字节称为前导字节（leading byte），后续字节称为连续字节（continuation bytes）。前导字节的高位通过 1 的个数表示序列中的总字节数。例如，从 U+0080 到 U+07FF 的码点编码的前导字节以 110 开头，表示整个编码长度为 2 个字节，因为有两个 1。连续字节的高位始终为 10。然后将码点的二进制表示划分到前导字节和连续字节的低位。
以下编码过程摘自维基百科 UTF-8 英文页面：
考虑对欧元符号
€进行编码，其 Unicode 码点是U+20AC。码点在
U+0800到U+FFFF范围内，所以需要三个字节来存储。0x20AC的二进制表示有 14 个有效位。前导补充两个 0 后，
0x20AC的二进制形式是00100000 10101100。我们来计算 UTF-8 编码的前导字节。高位是固定的
1110，表示三字节序列。低位存储码点的 4 个最高位。该字节最终形式为11100010。码点还有 12 位需要编码。接下来，我们来计算第一个连续字节。高位固定为
10，低位存储码点的接下来的 6 位。该字节是10000010。码点还有 6 位需要编码。最后，我们来计算最后一个连续字节。高位固定为
10，低位存储码点的最后 6 位。这个字节是10101100。由此最终的三字节序列是
11100010 10000010 10101100，可以更简洁地写为十六进制，如e2 82 ac。
你的任务是编写 to_utf8 函数，该函数接收一个 Unicode 码点并构造出 UTF-8 编码的字节序列。
int to_utf8(unsigned short code_point, unsigned char utf8_bytes[])
函数 to_utf8 有两个参数；一个 unsigned short 类型的 code_point 和一个字节数组 utf8_bytes。该函数将构造给定码点的 UTF-8 表示形式，并将编码字节序列写入数组 utf8_bytes 中。第一个字节（例如前导字节）应位于数组的索引 0 处，其余字节（如果有的话，例如连续字节）应位于索引 1 处，依此类推。utf8_bytes 数组由客户端提供，要保证有足够的空间可以容纳完整的 3 个字节，尽管可能只需要 1 或 2 个字节。后续课程会更深入讨论 C 数组，如果你传递一个数组作为参数，修改该数组的元素将修改原始数组，类似 C++ 中的引用参数，因此上面的函数可以传回它创建的字节。该函数返回值是编码的字节数（1、2 或 3）。
你将在提供的 utf8 程序中实现这个函数，该程序采用一个或多个码点，并使用 to_utf8 函数显示每个码点的 UTF-8 十六进制编码和相应的字符字形。以下一个运行示例：
$ utf8 0x41 0xfc 0x3c0 0x4751
U+0041 UTF-8 Hex: 41 Character: A
U+00FC UTF-8 Hex: c3 bc Character: ü
U+03C0 UTF-8 Hex: cf 80 Character: π
U+4751 UTF-8 Hex: e4 9d 91 Character: 䝑
此任务通过提取/重排/打包位模式，是构造位掩码并应用位运算的一个极好实践。
测试与提交#
你的程序是否正确，很大程度上依赖于你的测试用例是否完善。如果测试不到位，一些隐藏的漏洞将很难被发现。经过 CS101 的训练，对于 TDD 的测试用例编写，我们可以总结一些基本的规范：
黑盒测试：不需要了解程序的底层实现，以用户的视角来测试程序。一般要特别注意一些边界情况，比如作业 0 中的负值，比如一些参数类型不正确的情况。这些案例的编写需要你从客户视角，从多个角度思考真实场景下可能出现的问题。
白盒测试：需要你了解程序的底层实现。比如 CS101 中很多 ADT 都会包含一个
debug接口，直接测试数据结构的底层表示。压力测试：开发时用于测试的数据集一般较小，真实场景中很可能发生用户输入较多，造成程序崩溃的情况。
在编写作业代码时，一个很好的测试策略是使用测试驱动开发，如下所示：
确定一个小的具体任务（要修复的错误、要添加的功能、所需的行为更改）
为所需结果构建测试用例，并验证当前代码是否可以通过这些测试
修改代码，直到通过所有测试为止
测试系统的其余部分，以验证是否无意中破坏其他内容
每次只需要更改少量代码，并通过精心构造的测试用例来验证结果。这样可以让你的开发过程稳步向前，同时确保你在每一步都有一个完整的功能实现。
作为作业的一部分，你应该尽可能完善 custom_tests 中的测试案例，至少添加 3 到 5 个。为了更好的可读性，也建议你为代码和测试用例编写注释或文档。这些注释将提醒你添加的每个测试的初衷，以及这些测试之间的相互关系。
例如，程序 sat 可以测试不同的位宽、极值、范围内的总和以及溢出的总和。对于 automata，请仔细查看在生成过程中，哪些地方有特殊情况，并编写明确的测试用例解决这些问题。虽然你可以向 utf8 提供大约 65,000 个可能的码点，但考虑到它们只有几个不同的情况，因此针对每个情况的典型测试用例将更有意义，特别是边界处的情况。
更多测试的建议，可以阅读 Software Testing Strategies
提交前的检查#
作业提交方式参考作业 0，可以使用 submit 提交你的代码。为了追求完美，一些加分项值得你去注意：
编译是否干净，有无警告等编译错误？
默认测试是否全部通过？
自定义测试案例是否全面？
对于代码实现部分：
有没有其他地方，还可以使用位运算进行改写？
算法是否高效？还记得如何分析算法复杂度吗？
代码风格及可读性是否注意过？有没有进行函数拆分，提取出一些更通用的代码？
文档有没有尝试编写？一份好的代码就如同一篇优美的散文，不多一字，也不少一字。加油！
另外也鼓励你花点时间反思一下目前的状态，你已经掌握了哪些知识点和工具？还需要继续训练哪些新知识点和技能？完成这次作业后，你应该适应了 C 和命令行的使用，熟悉编写/编译/调试的过程。这是一个重要的里程碑！