Discussion 1: C语言与数值表示¶

预习：数值表示¶

在不同的上下文中，相同的比特序列可能表示不同的内容。

答案

正确。相同的比特在完全相同的情况下可以有多种不同的解释！这些比特可以表示无符号数、有符号数，甚至在我们之后将要学习的内容中，还可以表示一个程序。关键在于对它的解释是否达成了一致。
当用补码对两个符号相反的数进行加法时，可能会发生溢出。

答案

错误。溢出错误只会在加法的正确结果超出范围 $[-(2^{n-1}), \quad 2^{n-1} - 1]$ 时发生。给符号相反的数相加不会导致结果超出这个范围。
如果将一个 $N$ 位的补码按无符号数解释，那么负数会被解释为小于正数的值。

答案

错误。在补码表示法中，负数的最高有效位（MSB）总是 1。这意味着每一个负数在转换为无符号数时，其值都会比所有正数更大。
如果将一个 $N$ 位的移码按无符号数解释（假设存在负数时的偏移量），那么负数会被解释为小于正数的值。

答案

正确。在移码表示法中，我们通过给无符号数加上一个偏移值来表示数值。无论我们如何“平移”可表示值的范围，负数在转换为无符号数时，总是比正数小。这一点不同于补码（见上文说明）。
我们可以在给定的数值表示格式（无符号、移码和补码）中表示分数和小数。

答案

错误。我们目前的表示格式有一个主要的限制：只能表示整数并对整数进行运算。要想成功表示小数以及超出当前范围的极大数值，我们需要另一种表示格式。

C 与数值表示¶

无符号和有符号整数¶

将下列数字从其初始进制转换为其他两种常用进制：
(a) 0b10010011
(b) 0
(c) 437
(d) 0x0123

答案

(a) Decimal: 147, Hex: 0x93

(b) Binary: 0b0, Hex: 0x0

(c) Binary: 0b110110101, Hex: 0x1B5

(d) Binary: 0b100100011, Decimal: 291
将下列数字从十六进制转换为二进制：
(a) 0xD3AD
(b) 0x7EC4

答案

(a) 0b1101001110101101

(b) 0b0111111011000100
假设使用 8 位整数且偏移为 −127（如适用），下列表示法中最大的整数是什么？将该数加 1 会得到什么结果？
(a) 无符号
(b) 移码
(c) 补码

答案

(a) Largest: 255, Largest + 1: 0

(b) Largest: 128, Largest + 1: -127

(c) Largest: 127, Largest + 1: -128
如何表示数字 0、1 和 −1？请分别以二进制和偏移 −127（如适用）表示。
(a) 无符号
(b) 移码
(c) 补码

答案

(a) 0: 0b0000 0000, 1: 0b0000 0001, −1: N/A

(b) 0: 0b0111 1111, 1: 0b1000 0000, −1: 0b0111 1110

(c) 0: 0b0000 0000, 1: 0b0000 0001, −1: 0b1111 1111
如何表示数字 17 和 −17？请分别以二进制和偏移 −127（如适用）表示。
(a) 无符号
(b) 移码
(c) 补码

答案

(a) 17: 0b0001 0001, −17: N/A

(b) 17: 0b1001 0000, −17: 0b0110 1110

(c) 17: 0b0001 0001, −17: 0b1110 1111
使用任意一种仅用 8 个比特（bit）的编码方案，能够表示的最大整数是多少？

答案

并不存在这样一个确定的最大整数。例如，一个任意的 8 位编码方案可以选择表示从 1 到 256 的整数，而不是通常认为的从 0 到 255。
证明：若将二进制数的各位反转得到 $x$，则 $x + x + 1 = 0$。

答案

考虑一下执行 𝑥 + 𝑥 时会发生什么。在每个 "位"上，我们要么看到 𝑥 在该 "位"上有一个 0 位，即 𝑥 在该 "位"上有一个 1 位，要么相反。无论哪种情况，加上 0b1 + 0b0 = 0b1，即无论𝑥的值是多少，𝑥 + 𝑥 = 0b111...111。在此基础上加 1 会导致溢出，结果是 0。
（选做）利用你在问题 2.7 中的结果，证明：$n$ 位补码数值 $d_{n-1}d_{n-2}\cdots d_0$ 表示的数值为
$$ -2^{n-1}d_{n-1} \;+\; \sum_{i=0}^{n-2} 2^i d_i, $$

答案

当最高位（MSB）为 0 时，该数的数值与同样位模式的无符号数完全相同。现在考虑最高位为 1 的情形。理解这一点的最简便方法，是思考一个形如 0b10...00 二进制数的值具体应该是多少。为了更清楚地说明问题，我们以一个 4 位宽度的二进制数 0b1000 为例。考虑与其相加得到 0b10000（即 5 位数，发生溢出后变为 0）的数值必定是 0b0111 + 0b0001，其值为 $2^2 + 2^1 + 2^0 + 2^1 = 2^3$。因此，我们可推断出最高位（MSB）表示的实际值为 $-2^3$ 。进一步推广至一般情况，对于 $n$ 位补码数值而言，最高位（MSB）代表的数值就是 $2^{n-1}$

算术与计数¶

计算下列涉及 6 位补码数的算术表达式的十进制结果，就像计算机中那样。哪些会产生溢出？所有操作是否都可行？
(a) 0b011001 - 0b000111
(b) 0b100011 + 0b111010
(c) 0x3B + 0x06
(d) 0xFF - 0xAA
(e) 0b000100 - 0b001000

答案

(a) 0b010010 = 18, 无溢出。

(b) 相加得到 0b1011101，但是由于我们使用的是 6 位数，我们截断第一个数字，得到 0b011101 = 29。由于我们将两个负数相加的结果是一个正数，这导致了溢出。

(c) 转换为二进制后，我们得到 0b111011 + 0b000110 = （截断后，因为问题说明我们使用的是 6 位数）0b000001 = 1。尽管多了一个截断位，但这并不是溢出，因为 -5 + 6 确实等于 1！

(d) 骗人的问题！这是不可能的，因为这些十六进制数需要 8 位来表示，而我们使用的是 6 位数。

(e) 0b001000 的补码是 0b110111 + 1 = 0b111000。我们将其与 0b000100 相加，得到 0b111100。我们可以通过将所有内容转换成小数来检查一遍：0b000100 是 4，0b001000 是 8，所以减法的结果应该是-4，即 0b111100。
下列方案能表示多少个不同的数？其中有多少个是正数？
(a) 10 位无符号
(b) 8 位补码
(c) 6 位移码，偏移为 −30
(d) 10 位原码

答案

(a) 1024, 1023. 在无符号表示法中，不同的比特 - 字符串对应不同的数字，因此 10 bits 可以表示 $2^{10} = 1024$ 个不同的数字。在所有这些数字中，只有数字 0 是非正数，因此我们可以表示 1023 个不同的正数。

(b) 256, 127. 与无符号一样，不同的比特 - 字符串在二进制中对应不同的数字，因此 8 bits 可以表示 $2^8 = 256$ 个数字。在这些数字中，有一半的 MSB 是 1，是负数，还有一个是 0，因此我们可以表示 $\frac{256}{2} - 1 = 127$ 个不同的正数。

(c) 64, 33. 和无符号一样，在移码表示中，没有两个不同的比特 - 字符串对应相同的数字，因此 6 bits 可以表示 $2^6 = 64$ 个数字。在这种偏置下，我们能表示的最大数字是 0b111111= 63 - 30 = 33，最小的是-30，因此有 33 个不同的正数（1 - 33）。

(d) 1023, 511. 两个不同的比特 - 字符串（0b0000000000 和 0b1000000000）对应于同一个数字 0，因此我们只能表示 $2^{10}$。 - 其中，除了 0b0000000000 之外，每个 MSB 为 0 的比特 - 字符串都对应一个不同的正数，因此我们可以表示 $2^9 - 1 = 511$ 个不同的正数。

预习：C 语言简介¶

声明字符数组的正确方式是 char[] array。

答案

错误。正确的写法是 char array[]。
C 是按值传递语言。

答案

正确。如果你想传递引用（reference），应该使用指针。
在编译型语言中，编译时间通常很快，但运行时速度明显慢于解释型语言。

答案

错误。合理的编译时间，出色的运行性能。编译型语言能针对特定的处理器类型和操作系统进行优化。
什么是指针？它与数组变量有何共同点？

答案

我们常说，"一切都只是比特"。指针只是一个比特序列，被解释为内存地址。一个数组就像一个指针，指向为该数组分配的内存中的第一个元素。不过，数组名称不是变量，也就是说，&arr = arr 而 &ptr != ptr，除非发生了什么神奇的事情（这是什么意思？）
如果尝试对非指针变量进行解引用，会发生什么？如果对已释放的指针进行解引用，又会怎样？

答案

它会将该变量的底层位视为指针，并尝试访问其中的数据。C 语言几乎可以让你做任何你想做的事情，不过如果你试图访问一个 "非法"内存地址，它就会出现故障，原因我们将在本课程后面学习。这就是为什么 C 语言不被认为是 "内存安全 "的原因：稍有不慎，就会自取灭亡。如果你释放了一个变量，而这个变量之前已经被释放过，或者没有被alloc过/调用过/重新分配过，那么就会发生不好的事情。这种行为是未定义的，会终止执行，导致 "无效释放"错误。
内存扇区由硬件定义，无法更改。

答案

错误。任何特定进程（应用程序）的栈、堆、静态/数据和文本/代码这四个主要内存扇区都是由操作系统定义的，并可能因其运行所需的内存类型而有所不同。一个进程可能需要很大的栈空间，但只需要很少的文本、静态和堆空间，这是什么情况？ (几乎所有基本的深度递归方案，因为你在不关闭前一个函数的情况下，会在每个函数上调用很多新函数，因此需要栈帧）。文本和静态重型进程的例子是什么？ (可能是一个非常复杂的进程，但它能高效地使用栈，而且不会动态分配内存）。有没有重用堆的进程的例子？ (可能是使用了大量用户试图访问的动态内存）。

谁来传参？¶

下列函数可能包含逻辑或语法错误。找出并纠正它们。

(a) 返回 summands 中所有元素之和。
```
1 int sum(int *summands) {
2     int sum = 0;
3     for (int i = 0; i < sizeof(summands); i++)
4         sum += *(summands + i);
5     return sum;
6 }
```
(b) 将存储在数组开头的字符串中的所有字符递增 n 次（n ≤ strlen(string)），不修改数组的其他部分。
```
1 void increment(char *string, int n) {
2     for (int i = 0; i < n; i++)
3         *(string + i)++;
4 }
```
(c) 如果有足够空间，则将输入字符串 src 覆盖为 “61C is awesome!”，否则不做任何操作。假设 length 正确表示 src 的长度。
```
1 void cs61c(char *src, size_t length) {
2     char *srcptr, replaceptr;
3     char replacement[16] = "61C is awesome!";
4     srcptr = src;
5     replaceptr = replacement;
6     if (length >= 16) {
7         for (int i = 0; i < 16; i++)
8             *srcptr++ = *replaceptr++;
9     }
10 }
```
答案

(a) 在传递指针时还需要传递一个大小
```
int sum(int* summands, size_t n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
    sum += *(summands + i);
    return sum;
}
```
(b) 字符串的末尾用空结束符表示，而不用𝑛。仅仅在数组中留出 𝑛 个字符的空间并不意味着存储在数组中的字符串长度也是 n。
```
void increment(char* string) {
    for (i = 0; string[i] != 0; i++)
    string[i]++; // or (*(string + i))++;
}
```
此外，表达式 (string + i)+ + 的运算符优先级也不正确。 ++ 递增发生在取消引用操作符之前。因此，我们需要用括号 ((string + i))++ 包起来，或者使用数组下标（其优先级与取消引用相同），如 string[i]++。

另一个需要注意的常见错误是在以 0xFF 值递增字符时出现的边界情况。将 1 加到 0xFF 会溢出回到 0，产生一个空结束符，无意中缩短了字符串。

(c) char *srcptr，replaceptr 会初始化一个 char 指针，而不是两个 char 指针。

正确的初始化应该是 char *srcptr, *replaceptr。

实现下列函数，使其按描述工作。

(a) 交换两个 int 的值。函数返回后仍应保持交换状态。提示：答案大约三行代码。

1 void swap(________________, ________________) {
2
3 }

(b) 返回字符串的字节数。请勿使用 strlen。提示：答案大约五行代码。

1 int mystrlen(________________) {
2
3 }

答案

(a)

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

(b)

int mystrlen(char* str) {
    int count = 0;
    while (*str != 0) {
    str++;
    count++;
    }
    return count;
}