CSAPP2

本节主要研究数据的二进制表示，无符号、补码和浮点数的表示方法，以及基本的位级运算和算术运算。

十六进制表示：

下表对应了一个十进制、二进制和十六进制的对应表：

十进制	二进制	十六进制
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
10	1010	A
11	1011	B
12	1100	C
13	1101	D
14	1110	E
15	1111	F

Amdahl 定律

系统执行某应用程序时间 \(T_{old}\)，某部分初始所需求时间 \(\alpha T_{old}\) ，该部分提升性能 \(k\)，总执行时间为 \((1-\alpha) T_{old}+\frac{\alpha T_{old}}{k}\)

加速时间比 \(S=\frac{T_{old}}{T_{new}}=\frac{1}{(1-\alpha + \frac{\alpha}{k})}\)

字与字节

每台计算机都有字长，这决定了处理器一次能处理多少位数据。常见的字长有32位和64位。一个字通常由多个字节组成，每个字节包含8位。

所以字长为 \(w\) 的机器，虚拟地址的范围是 \(0\) 到 \(2^w - 1\)。

程序最多反应 \(2^w\) 个不同的内存单元，每个单元存储一个字节。

每个字节包含 8 位/字（bit），也称为位。

64位机器可以运行下面的32位机器编译的程序

gcc -m32 myprog.c

这样编译的程序就可以在64位和32位机器上运行。

如果允许

gcc -m64 myprog.c

就只能在64位机器上运行。

在 C 语言中，数据类型的大小与机器字长有关：

有符号	无符号	32位机器字节数	64位机器字节数
[signed] char	unsigned char	1	1
short	unsigned short	2	2
int	unsigned int	4	4
long	unsigned long	4	8
int32_t	uint32_t	4	4
int64_t	uint64_t	8	8
char *	char*	4	8
float	float	4	4
double	double	8	8

为了避免跨平台时出现数据类型大小不一致的问题，使用了 <stdint.h> 头文件中定义的固定宽度整数类型，如 int32_t 和 int64_t

不管是什么类型的指针，在32位机器上占4个字节，在64位机器上占8个字节。

这是因为指针永远指向的是内存地址，而内存地址的大小与机器字长有关。

大端和小端存储

对于跨多字节的程序，需要管理它在内存中是怎么排列的，由此产生了两种存储方式：大端（big-endian）和小端（little-endian）。

对于目前的地址 Addr，假设他存储一个32位的整数 \(0x12345678\)，那么：

800X400/1.png

如图所示，大端存储方式将最高有效字节（Most Significant Byte, MSB）存储在最低地址处，而小端存储方式则将最低有效字节（Least Significant Byte, LSB）存储在最低地址处。

直观来说，大端每个字节顺着地址增加存储，而小端每个字节逆着地址增加存储。

一般来说，有下面的情形采用大端存储：

• 网络协议（如 TCP/IP）通常采用大端存储。
• 某些 RISC 处理器（如 SPARC）采用大端存储。

而大多数现代计算机（如 x86 架构）采用小端存储。

程序的运行其实就是顺着地址来读取数据

在 C 语言中，可以通过强制类型转换来访问内存中的字节：

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len) {
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x) {
    show_bytes((byte_pointer)&x, sizeof(int));
}

void show_float(float x) {
    show_bytes((byte_pointer)&x, sizeof(float));
}

void show_pointer(void *x) {
    show_bytes((byte_pointer)&x, sizeof(void *));
}
int main() {
    int a = 0x12345678;
    float b = 1234.5678;
    void *p = &a;

    show_int(a);
    show_float(b);
    show_pointer(p);

    return 0;
}

这是在我本地运行的结果：

# ./1.exe
 78 56 34 12
 2b 52 9a 44
 3c fe 61 00 00 00 00 00

这个代码展示了如何通过字节指针访问整数、浮点数和指针的字节表示。

可以看到，整数 0x12345678 在内存中的字节顺序是 78 56 34 12

而浮点数通过后面的一种映射方式转换为了 2b 52 9a 44

而 \(a\) 的地址是 0x000000000061fe3c，在内存中的字节顺序是 3c fe 61 00 00 00 00 00

这说明我的机器采用小端存储方式，是 64 位机器。

CSAPP 练习题 2.5

思考 show_bytes 的三次调用

int val = 0x87654321;
byte_pointer valp = (byte_pointer)&val;
show_bytes(valp, 1);
show_bytes(valp, 2);
show_bytes(valp, 3);

在大端机器上输出结果是：

87
87 65
87 65 43

在小端机器上输出结果是：

21
21 43
21 43 65

对于字符，在内存中存储的是它的 ASCII 码值。

练习题 2.7

const char *s = "abcdef";
show_bytes((byte_pointer)s, strlen(s));

在小端机器上输出结果是：

61 62 63 64 65 66

在大端机器上输出结果是：

61 62 63 64 65 66

也就是说，不管是大端还是小端机器，字符串的字节顺序都是一样的，因为字符串是按顺序存储的，每个字符占一个字节。

布尔代数

从略，参考代数结构和数字电路相关章节

位级运算

C 语言中，位级运算符包括：

运算符	描述	示例	结果
&	按位与	5 & 3	1
|	按位或	5 | 3	7
^	按位异或	5 ^ 3	6
~	按位取反	~5	-6
<<	左移	5 << 1	10
>>	右移	5 >> 1	2

这些运算符可以用于整数类型的数据，按位操作其二进制表示。

练习 2.10

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

这个函数使用按位异或运算实现了两个整数的交换，而不需要使用临时变量。

步骤如下：

表格

步骤	*x	*y
初始	a	b
第1步	a	a ^ b
第2步	a ^ (a ^ b) = b	a ^ b
第3步	b	(a ^ b) ^ b = a

但是需要注意，如果 x 和 y 指向同一个地址，这个方法会导致结果为零。

这个方法没有性能上的优势

练习 2.11

void reverse_array(int a[], int cnt){
    int first, last;
    for(first = 0; last = cnt-1
       first <= last;
       first++, last--){
        inplace_swap(&a[first], &a[last]);
}

这个函数使用 inplace_swap 函数来交换数组中的元素，从而实现数组的反转。

但对奇数长度的数组，中间元素会被设成0。

如果把 first <= last 改为 first < last 就可以避免这个问题。

位级运算的一个常见用法为实现掩码（masking），即通过按位与操作来清除某些位，或通过按位或操作来设置某些位。

比如 x&0xFF 实现了取 x 的最低8位。

但是这样的代码可能不是可移植的。

练习 2.12

A. x 的最低有效字节，其余位置零

x & 0xFF

B. 除了 x 最低有效字节，其余位取补

x & ~0xFF

C. 最低有效字节置1

x | 0xFF

练习 2.13

bis 位设置：这是按位或操作，可以将指定的位设置为1。

int bis(int x, int m) {
    return x | m;
}

bic 位清除：这是按位与操作的补码，可以将指定的位清除为0。

int bic(int x, int m) {
    return x & ~m;
}

这两个函数可以实现或运算和异或运算

int bool_or(int x, int y) {
    return bis(x, y);
}

int bool_xor(int x, int y) {
    return bis(bic(x, y), bic(y, x));
}

逻辑运算

逻辑运算符包括： | 运算符 | 描述 | 示例 | 结果 | | :—-: | :–: | :–: | :–: | | && | 逻辑与 | 1 && 0 | 0 | | || | 逻辑或 | 1 || 0 | 1 | | ! | 逻辑非 | !1 | 0 |

逻辑运算符用于布尔值（true/false）之间的运算，结果也是布尔值。

在 C 语言中，对第一个表达式求值时，如果已经能够确定整个表达式的结果，就不会对第二个表达式求值，这称为短路求值（short-circuit evaluation）。

练习 2.15

只使用位级运算和逻辑运算等价于实现表达式 x==y

int is_equal(int x, int y) {
    return !(x ^ y);
}

移位运算

移位运算符包括左移（<<）和右移（>>）。

但是存在逻辑右移和算术右移的区别：

表格表示： | 右移操作 | 示例 | 结果 | | :——: | :–: | :–: | | 逻辑右移 | 0b11110000 >> 2 | 0b00111100 | | 算术右移 | 0b11110000 >> 2 | 0b11111100 |

简单来说，算术右移会保留符号位，而逻辑右移则不会。

事实上， C 语言中的右移操作对于有符号整数通常是算术右移，而对于无符号整数则是逻辑右移。

而 Java 中的右移操作符 >> 是算术右移，而 >>> 是逻辑右移。

整数表示

整数在计算机中通常使用补码（two’s complement）表示法。

首先区分几个概念

补码、反码、原码

原码：直接使用二进制表示整数的绝对值，最高位为符号位，0表示正数，1表示负数。

比如：

十进制	原码（8位）
5	00000101
-5	10000101

反码就是全部按位取反

补码是在反码的基础上加1

补码：对于正数，补码与原码相同；对于负数，补码是其反码加1。

为什么采用补码表示法呢？

因为如果使用反码表示法，会存在两个零（+0 和 -0），而补码表示法只有一个零。

而原码表示法在进行加减运算时需要额外处理符号位，增加了复杂性。

在使用逻辑门实现加法器时，补码表示法可以简化电路设计，因为加法器可以直接处理补码而不需要考虑符号位。

数值范围不在讨论，由于上述给出了在不同机器上不同类型的字节数，可以计算出对应的数值范围。

无符号数的编码

无符号整数使用二进制表示，范围从 0 到 \(2^w - 1\)，其中 \(w\) 是字长（以位为单位）。

无符号整数使用二进制表示法 (Binary to Unsigned, \(B2U\))。

• 定义公式：对于一个 \(w\) 位的向量 \(\vec{x} = [x_{w-1}, x_{w-2}, \dots, x_0]\)： \[B2U_w(\vec{x}) = \sum_{i=0}^{w-1} x_i 2^i\]
• 范围：从 \(0\) 到 \(2^w - 1\)。
  • 最小值 (\(UMin\))：全 0 \(\rightarrow 0\)。
  • 最大值 (\(UMax\))：全 1 \(\rightarrow 2^w - 1\)。

有符号数的编码

有符号整数通常使用补码表示法，范围从 \(-2^{w-1}\) 到 \(2^{w-1} - 1\)。

有符号整数最常见的表示法是补码 (Two’s Complement, \(B2T\))。

• 定义公式：最高位 \(x_{w-1}\) 被定义为符号位 (Sign Bit)，其权重为 \(-2^{w-1}\)： \[B2T_w(\vec{x}) = -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i\]
• 范围：从 \(-2^{w-1}\) 到 \(2^{w-1} - 1\)。
  • 最小值 (\(TMin\))：位向量为 \([1, 0, \dots, 0]\) \(\rightarrow -2^{w-1}\)。
  • 最大值 (\(TMax\))：位向量为 \([0, 1, \dots, 1]\) \(\rightarrow 2^{w-1} - 1\)。
• 特殊数值：
  • -1 的补码：全 1（例如 8 位时为 1111 1111）。
  • 0 的补码：全 0。

它们的编码是唯一的，证明简单，略

这几个特殊数值有关系：

\(|TMin|=|TMax|+1\)

\(UMax=2TMax+1\)

C 语言的库里面 <limits.h> 头文件定义了各种整数类型的最大值和最小值

扩展

有符号数的反码表示：

反码表示法（Binary to Ones’ Complement, \(B2O\)）现在已很少在现代计算机中使用，但在某些早期的数字逻辑中存在。

• 定义公式：最高位 \(x_{w-1}\) 为符号位，其权重为 \(-(2^{w-1} - 1)\)： \[B2O_w(\vec{x}) = -x_{w-1}(2^{w-1} - 1) + \sum_{i=0}^{w-2} x_i 2^i\]
• 范围：从 \(-(2^{w-1} - 1)\) 到 \(2^{w-1} - 1\)。
  • 以 8 位为例：范围是 \(-127\) 到 \(127\)。
• 特点：
  • 正数：与原码、补码一致。
  • 负数：符号位为 1，数值位是正数对应位的按位取反。
  • 存在“两个零”：
    • \(+0\) 的位模式为 00...0。
    • \(-0\) 的位模式为 11...1（全 1）

有符号数的原码表示：

原码表示法（Binary to Sign-Magnitude, \(B2S\)）是最接近人类直觉的表示方式，最高位仅作为符号标志，不参与数值权重计算。

• 定义公式：最高位 \(x_{w-1}\) 为符号位，决定正负，其余位计算绝对值： \[B2S_w(\vec{x}) = (-1)^{x_{w-1}} \cdot \left( \sum_{i=0}^{w-2} x_i 2^i \right)\]
• 范围：从 \(-(2^{w-1} - 1)\) 到 \(2^{w-1} - 1\)。
  • 以 8 位为例：范围是 \(-127\) 到 \(127\)。
• 特点：
  • 直观：最高位为 1 表示负，0 表示正，后面 \(w-1\) 位直接表示数值。
  • 存在“两个零”：
    • \(+0\) 的位模式为 00...0。
    • \(-0\) 的位模式为 10...0（符号位为 1，其余全 0）。
  • 运算复杂：在硬件实现上，原码的加减法非常麻烦，需要根据符号位判断是做加法还是减法，且减法还要处理借位。

整数的转换

C 语言的强制类型转换是保持地址即二进制表示不变的情况下，将数据解释为另一种类型。

如果将一个无符号整数转换为有符号整数，或者将一个较大类型的整数转换为较小类型的整数，可能会导致数值溢出或截断。

补码转化为无符号数

将补码 \(x\) 转换为 \(w\) 位的无符号数时，位模式不变。如果 \(x\) 为负，最高位的权重由 \(-2^{w-1}\) 变为 \(+2^{w-1}\)，数值上相当于加上了 \(2^w\)。

公式： \[T2U_w(x) = \begin{cases} x + 2^w, & x < 0 \\ x, & x \ge 0 \end{cases}\]

• 直观理解：
  • 如果 \(x\) 是非负数（最高位为 0），转换后数值不变。
  • 如果 \(x\) 是负数（最高位为 1），转换后的结果是一个很大的正数（即 \(x + 2^w\)）。
  • 例子 (\(w=16\))：补码 -1 的位模式是全 1，转化为无符号数后是 65535 ($ -1 + 2^{16} $)。

无符号数转化为补码

公式： \[U2T_w(u) = \begin{cases} u, & u \le 2^{w-1} - 1 \quad (即 \le TMax_w) \\ u - 2^w, & u > 2^{w-1} - 1 \quad (即 > TMax_w) \end{cases}\]

• 直观理解：
  • 如果无符号数 \(u\) 小于等于补码最大值（最高位为 0），转换后数值不变。
  • 如果无符号数 \(u\) 大于补码最大值（最高位为 1），转换后它会变成一个负数，数值减去 \(2^w\)。
  • 例子 (\(w=16\))：无符号数 50000（二进制最高位为 1），转化为补码后是 50000 - 65536 = -15536。

在 C 语言中，如果同时对有符号数和无符号数进行运算，通常会将有符号数转换为无符号数，以避免负数的出现。

这是隐式转换

扩展位

无符号数的零扩展

将一个 \(w\) 位的无符号数转换为 \(w'\) 位（其中 \(w' > w\)）时，直接在原始位模式的高位填充 \(0\)。

• 操作方法： 若原始位向量为 \([x_{w-1}, x_{w-2}, \dots, x_0]\)，扩展后的位向量为： \[[\underbrace{0, 0, \dots, 0}_{w'-w}, x_{w-1}, x_{w-2}, \dots, x_0]\]
• 结果特性：数值保持不变。
  • 由于填充的是高位零，其权重在无符号表示中不影响最终求和结果。
• 示例： 将 8 位无符号数 141 (1000 1101) 扩展为 16 位： 结果为 0000 0000 1000 1101，数值仍为 141。

有符号数的零扩展

注意： 对于有符号数，通常使用的是“符号扩展”来保持数值不变。但如果强制进行“零扩展”，其行为如下：

• 操作方法： 无视原始数的符号位（最高位），在高位一律填充 \(0\)。
• 结果特性：可能会改变数值。
  • 如果是正数（符号位为 0）：扩展后的数值保持不变。
  • 如果是负数（符号位为 1）：扩展后的数值会发生剧变。原始的负权重（最高位）在新的字长中变成了正权重，结果会变成一个巨大的正数。
• 示例 (8位扩展至16位)： 有符号数 -1 的 8 位补码为 1111 1111。 进行零扩展后得到：0000 0000 1111 1111。 此时数值变成了 255（不再是 -1）。

有符号数的符号扩展

有符号数扩展是指将一个 \(w\) 位的补码数字转换为 \(w'\) 位（其中 \(w' > w\)）时，为了保持其数值不变而采用的方法。

• 操作方法： 取原始位向量的符号位 \(x_{w-1}\)，并将其副本填充到所有新增的高位上。 若原始位向量为 \([x_{w-1}, x_{w-2}, \dots, x_0]\)，扩展后的位向量为： \[[\underbrace{x_{w-1}, x_{w-1}, \dots, x_{w-1}}_{w'-w}, x_{w-1}, x_{w-2}, \dots, x_0]\]

• 核心特性：数值完全保持不变。

  • 正数（符号位为 0）：高位全部补 0，数值不变（与无符号数零扩展效果一致）。
  • 负数（符号位为 1）：高位全部补 1，数值依然保持不变。

• 示例： 假设字长从 8 位扩展到 16 位：

  1. 正数 +5：
     • 8 位补码：0000 0101
     • 符号扩展后：0000 0000 0000 0101（数值仍为 5）
  2. 负数 -5：
     • 8 位补码：1111 1011
     • 符号扩展后：1111 1111 1111 1011（数值仍为 -5）

• 原理证明（直观理解）： 在补码中，最高位的权重是负的。当我们把 8 位的 -128 (1000 0000) 扩展为 9 位时，原来的符号位权重从 \(-2^7\) 变成了新符号位的权重 \(-2^8\)。为了补偿这个差值，我们需要在新增的位上填 1（权重为 \(+2^7\)），因为 \(-2^8 + 2^7 = -2^7\)。以此类推，无论扩展多少位，只要填充符号位，数值就会守恒。

练习 2.23

考虑下面的函数

int fun1(unsigned word){
    return (int)((word << 24) >> 24);
}

int fun2(unsigned word){
    return ((int)word << 24) >> 24;
}

在采用补码运算的 32 位机器上

第一个函数实现了

提取 word 的低 8 位（最低字节），并进行零扩展。

• 过程分析：
  1. word << 24：将最低的 8 位移动到最左边的最高 8 位，右边补 24 个 0。
  2. >> 24：由于 word 是 unsigned 类型，这里的右移是逻辑右移。高位会补 24 个 0。
  3. 结果：高 24 位全部变为 0，低 8 位保留了原 word 的低 8 位。
• 效果：相当于 word & 0xFF。无论原低 8 位的最高位（第 7 位）是 0 还是 1，结果永远是一个 [0, 255] 之间的正整数。

第二个函数实现了

提取 word 的低 8 位（最低字节），并进行符号扩展。

• 过程分析：
  1. (int)word：先将无符号数强制转换为有符号 int。
  2. << 24：左移 24 位，将原低 8 位移至最高字节。此时，原低 8 位的最高位（第 7 位）变成了整个 32 位整数的符号位。
  3. >> 24：由于此时操作数是 int（有符号），这里的右移是算术右移。算术右移会根据符号位来填充高位：
     • 如果低 8 位的第 7 位是 0，则高位补 0。
     • 如果低 8 位的第 7 位是 1，则高位补 1。
• 效果：将低 8 位解释为一个 8 位的补码。如果低 8 位在 8 位表示法下是负数，结果就是 32 位的负数；如果是正数，结果就是 32 位正数。结果范围是 [-128, 127]。

截断

无符号数的截断

将一个 \(w\) 位的无符号数 \(x\) 截断为 \(k\) 位时，高 \(w-k\) 位会被直接丢弃。

• 公式： \[x' = x \pmod{2^k}\]
• 位级表示： 若原始位向量为 \([x_{w-1}, x_{w-2}, \dots, x_0]\)，截断后的位向量为 \([x_{k-1}, x_{k-2}, \dots, x_0]\)。
• 直观理解： 截断操作相当于对 \(2^k\) 取模。例如，将一个 16 位的无符号数截断为 8 位，其结果就是该数除以 256 (\(2^8\)) 的余数。

有符号数的截断

有符号数的截断在位级上的操作与无符号数完全相同（即直接丢弃高位），但由于最高位权重的改变，其数值解释会发生变化。

• 公式： \[x' = U2T_k(x \pmod{2^k})\] （先将原始位向量视为无符号数进行取模截断，再将结果转换为 \(k\) 位的补码。）
• 操作步骤：
  1. 丢弃高 \(w-k\) 位。
  2. 将剩余的 \(k\) 位中，第 \(k-1\) 位（新的最高位）解释为符号位。
• 结果特性： 截断有符号数不仅可能改变数值的大小，还可能改变符号。
• 示例： 将数值 53191（16位补码/无符号均为 1100 1111 1100 0111）截断为 8 位：
  1. 丢弃高 8 位，剩下 1100 0111。
  2. 作为无符号数解释，它是 199。
  3. 作为 8 位补码解释，最高位是 1，其值为 199 - 256 = -57。

有符号数到无符号数的隐式强制类型转换导致了某些非直观的 行为。而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差 别的错误很难被发现。

练习 2.25

代码如下：

/* WARNING: This is buggy code */
float sum_elements(float a[], unsigned length) {
    int i;
    float result = 0;

    for (i = 0; i <= length-1; i++)
        result += a[i];
    return result;
}

分析与解答：

原因：参数 length 是 unsigned（无符号）类型。当调用函数且 length 等于 0 时，表达式 length - 1 会进行无符号运算。在无符号运算中，0 - 1 会导致溢出，结果变成无符号类型所能表示的最大值（例如在 32 位机器上是 4294967295）。因此，循环条件 i <= length - 1 变成了 i <= 4294967295，循环会不停执行并尝试访问数组 a 之外的内存，最终导致内存错误（如段错误）。

修改方法：将循环条件改为使用简单的比较，避免对 length 进行减法操作：

float sum_elements(float a[], size_t length) {
    size_t i; 
    float result = 0;

    for (i = 0; i < length; i++)
        result += a[i];
    return result;
}

练习 2.26

代码如下：

/* Prototype for library function strlen */
size_t strlen(const char *s);

/* Determine whether string s is longer than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, char *t) {
    return strlen(s) - strlen(t) > 0;
}

解答：

A. 在什么情况下，这个函数会产生不正确的结果？ 当字符串 s 的长度小于字符串 t 的长度时（即 strlen(s) < strlen(t)），函数会产生不正确的结果。在这种情况下，它会错误地返回 1（真）。

B. 解释为什么会出现这样不正确的结果。 因为 strlen 函数返回的类型是 size_t，这是一个无符号整数类型。在 C 语言中，当两个无符号数进行运算时，结果也是无符号的。如果 strlen(s) 小于 strlen(t)，它们的差本应该是负数，但在无符号运算中，这个结果会发生溢出，变成一个巨大的正整数。由于这个巨大的正整数大于 0，所以除非两个字符串长度完全相等，表达式 strlen(s) - strlen(t) > 0 的结果永远为真。

C. 说明如何修改这段代码让它能可靠地工作。 应该直接比较两个长度的值，而不是将它们相减：

int strlonger(char *s, char *t) {
    return strlen(s) > strlen(t);
}

加法

无符号的加法

无符号加法等价于计算和的模运算。假设字长为 \(w\) 位。

• 定义公式： 对于 \(0 \le x, y < 2^w\)： \[x +^u_w y = \begin{cases} x + y, & x + y < 2^w \quad (\text{正常}) \\ x + y - 2^w, & x + y \ge 2^w \quad (\text{溢出}) \end{cases}\]
• 模运算解释：\(x +^u_w y = (x + y) \pmod{2^w}\)。
• 溢出判定： 令 \(s = x +^u_w y\)。当且仅当 \(s < x\) (或 \(s < y\)) 时，发生了无符号溢出。
• 特点： 溢出后的结果会比实际的和“变小”，因为它丢弃了第 \(w\) 位的进位（Carry-out）。

有符号的加法

有符号加法（补码加法）在位级上与无符号加法一致，但其结果需要通过补码规则解释，且可能发生正溢出或负溢出。

• 定义公式： 令 \(s = x + y\)（真实的数学和），\(w\) 为字长： \[x +^t_w y = \begin{cases} x + y - 2^w, & 2^{w-1} \le x + y \quad (\text{正溢出}) \\ x + y, & -2^{w-1} \le x + y < 2^{w-1} \quad (\text{正常}) \\ x + y + 2^w, & x + y < -2^{w-1} \quad (\text{负溢出}) \end{cases}\]
• 溢出判定（非常重要）：
  1. 正溢出 (Positive Overflow)：当 \(x > 0, y > 0\) 但结果 \(s \le 0\) 时。
     • 现象：两个很大的正数相加，结果变成了负数。
  2. 负溢出 (Negative Overflow)：当 \(x < 0, y < 0\) 但结果 \(s \ge 0\) 时。
     • 现象：两个很小的负数相加，结果变成了正数。
  3. 注意：符号不同的两个数相加（一正一负）永远不会发生溢出。

硬件层面上，他们都是使用的加法器，所以底层实现都是一样的，直接相加截断即可

乘法类似

练习 2.30

写出一个具有如下原型的函数：

/* Determine whether arguments can be added without overflow */
int tadd_ok(int x, int y);

如果参数 x 和 y 相加不会产生溢出，这个函数就返回 1。

解答：

int tadd_ok(int x, int y) {
    int sum = x + y;
    int neg_over = x < 0 && y < 0 && sum >= 0;
    int pos_over = x > 0 && y > 0 && sum <= 0;
    return !neg_over && !pos_over;
}

原理：当且仅当两个正数相加得到负数（正溢出），或者两个负数相加得到非负数（负溢出）时，补码加法才发生溢出。

练习 2.31

你的同事对你补码加法溢出条件的分析有些不耐烦了，他给出了一个函数 tadd_ok 的实现，如下所示：

/* Determine whether arguments can be added without overflow */
/* WARNING: This code is buggy. */
int tadd_ok(int x, int y) {
    int sum = x + y;
    return (sum - x == y) && (sum - y == x);
}

你看了代码以后笑了。解释一下为什么。

解答：

这个实现是错误的，因为补码加法在位级运算上形成了一个阿贝尔群。在计算机的模运算中，无论 x + y 是否溢出，(x + y) - x 的结果在位级表示上永远等于 y。

即使 x + y 发生了溢出并导致丢弃了进位，减去 x 的操作会以完全相同的方式进行回绕，从而抵消掉溢出的影响。换句话说，在补码运算中，(x + y) - x == y 这个恒等式总是成立的，因此这个函数永远会返回 1，无法检测出溢出。

练习 2.32

你现在有个任务，编写函数 tsub_ok 的代码，函数的参数是 x 和 y，如果计算 x - y 不产生溢出，函数就返回 1。假设你写的练习题 2.30 的代码如下所示：

/* Determine whether arguments can be subtracted without overflow */
/* WARNING: This code is buggy. */
int tsub_ok(int x, int y) {
    return tadd_ok(x, -y);
}

x 和 y 取什么值时，这个函数会产生错误的结果？写一个该函数的正确版本。

解答：

A. 产生错误结果的情况： 当 y 等于 TMin（补码表示的最小负整数，例如 32 位下的 -2147483648）时，该函数会产生错误结果。

B. 错误原因： 在补码运算中，TMin 的相反数仍然是它本身（即 -TMin = TMin）。 当 y = TMin 时，调用 tadd_ok(x, -y) 实际上等同于调用 tadd_ok(x, TMin)。 举例：如果 x = -1, y = TMin。实际计算 x - y 等于 -1 - (-2147483648) = 2147483647 (TMax)，这并没有溢出。 然而，函数内部执行 tadd_ok(-1, TMin) 会检测两个负数相加。因为 -1 + TMin 等于 -2147483649，超出了表示范围，tadd_ok 会判定为发生负溢出并返回 0。这导致 tsub_ok 在本该返回 1 的时候返回了 0。

C. 正确版本：

int tsub_ok(int x, int y) {
    /* 特殊处理 y 等于 TMin 的情况，或者直接根据符号判定 */
    int res = x - y;
    int pos_over = x >= 0 && y < 0 && res < 0;
    int neg_over = x < 0 && y >= 0 && res >= 0;
    return !pos_over && !neg_over;
}

或者使用已经写好的 tadd_ok，但要单独处理 y = TMin：

int tsub_ok(int x, int y) {
    /* 如果 y 是 TMin 且 x 是负数，x - TMin 永远不会溢出 (结果在 [0, TMax]) */
    /* 如果 y 是 TMin 且 x 是非负数，x - TMin 永远会溢出 (结果 >= TMax + 1) */
    if (y == -2147483647 - 1) { /* 这里的写法是为了兼容某些编译器对 TMin 直接量的处理 */
        return x < 0;
    }
    return tadd_ok(x, -y);
}

练习 2.35

题目：给你一个任务，开发函数 tmult_ok 的代码，该函数会判断两个参数相乘是否会产生溢出。下面是你的解决方案：

/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
    int p = x * y;
    return !x || p / x == y;
}

按照下面的思路，用数学推导来证明你的方法是对的。考虑 \(w\) 位数字 \(x (x \neq 0)\)、 \(y\)、\(p\) 和 \(q\)，这里 \(p\) 是 \(x\) 和 \(y\) 补码乘法的结果，而 \(q\) 是 \(p\) 除以 \(x\) 的结果。

1. 说明 \(x\) 和 \(y\) 的整数乘积 \(x \cdot y\) 可以写成这样的形式： \(x \cdot y = p + t 2^w\)，其中 \(t \neq 0\) 当且仅当 \(p\) 的计算溢出。
2. 说明 \(p\) 可以写成这样的形式： \(p = x \cdot q + r\)，其中 \(|r| < |x|\)。
3. 说明 \(q = y\) 当且仅当 \(r = t = 0\)。

解答：

1. 根据补码乘法定义，\(p\) 是真实乘积 \(x \cdot y\) 截断为 \(w\) 位后的值。在数学上，截断操作相当于 \(x \cdot y \pmod{2^w}\)，因此 \(x \cdot y\) 与 \(p\) 之差必然是 \(2^w\) 的整数倍，即 \(x \cdot y = p + t 2^w\)。当且仅当 \(t \neq 0\) 时，说明真实乘积超出了 \(w\) 位表示范围，即发生了溢出。

2. 这是整数除法的基本性质，其中 \(q\) 是商，\(r\) 是余数，且余数范围满足 \(0 \le |r| < |x|\)。

3. 若 \(q = y\)，代入公式有 \(p = x \cdot y + r\))

   \(p = x \cdot y - t 2^w\)，可得 \(x \cdot y + r = x \cdot y - t 2^w\)，即 \(r = -t 2^w\)。由于 \(|r| < |x| \le 2^{w-1}\)，而若 \(t \neq 0\) 则 \(|-t 2^w| \ge 2^w\)。一个绝对值小于 \(2^{w-1}\) 的数不可能等于一个绝对值大于等于 \(2^w\) 的数，除非两者均为 \(0\)。因此 \(t\) 必须为 \(0\)（无溢出），且 \(r\) 必须为 \(0\)。

练习 2.36

题目：对于数据类型 int 为 32 位的情况，设计一个版本的 tmult_ok 函数，使用 64 位精度的数据类型 int64_t ，而不使用除法。

解答：

#include <stdint.h>

int tmult_ok(int x, int y) {
    /* 使用 64 位整数保存完整的数学乘积 */
    int64_t p = (int64_t)x * y;
    /* 如果强转回 32 位后数值不变，说明没有溢出 */
    return p == (int)p;
}

补码的非

-x=~x+1

除了对于最小负数 TMin，因为 ~TMin + 1 = TMin

乘常数

做位移运算

对于某个常数 \(k\) 的表达式 \(x \cdot k\)：

1. 乘以 2 的幂 当 \(k = 2^k\) 时，\(x \cdot 2^k\) 可以等价地表示为 \(x \ll k\)。

2. 乘以任意常数 编译器会将 \(k\) 的二进制表示表达为一组连续的 \(1\)。考虑从位位置 \(n\) 到位位置 \(m\) 的一段连续的 \(1\) (\(n \ge m\))，可以利用以下两种形式计算这些位对乘积的影响：

形式 A：\((x \ll n) + (x \ll (n-1)) + \dots + (x \ll m)\) 这是基于加法法则，将每一个权重为 \(1\) 的位对应的移位结果相加。

形式 B：\((x \ll (n+1)) - (x \ll m)\) 这是基于属性 \(2^n + 2^{n-1} + \dots + 2^m = 2^{n+1} - 2^m\)。当连续的 \(1\) 较多时，形式 B 只需要两次移位和一次减法，效率更高。

例如，计算 \(x \cdot 14\)： 由于 \(14\) 的二进制为 \(1110\)（即 \(n=3, m=1\)），可以表示为： 形式 A：\((x \ll 3) + (x \ll 2) + (x \ll 1)\) 形式 B：\((x \ll 4) - (x \ll 1)\)

练习题 2.38

题目： 考虑 \(b\) 等于 \(0\) 或者等于 \(a\)、\(k\) 为任意可能的值的情况，用一条 LEA 指令可以计算 \(a\) 的哪些倍数？

解答： 根据 LEA 指令的形式 \((a \ll k) + b\)，其中 \(k \in \{0, 1, 2, 3\}\)。 1. 当 \(b = 0\) 时，可以计算的倍数为 \(a \cdot 2^k\)。此时倍数为：\(2^0=1, 2^1=2, 2^2=4, 2^3=8\)。 2. 当 \(b = a\) 时，可以计算的倍数为 \(a \cdot 2^k + a = a \cdot (2^k + 1)\)。此时倍数为：\(2^0+1=2, 2^1+1=3, 2^2+1=5, 2^3+1=9\)。 综合以上情况，一条 LEA 指令可以计算 \(a\) 的倍数集合为：\(\{1, 2, 3, 4, 5, 8, 9\}\)。

---

练习题 2.39

题目： 对于位位置 \(n\) 为最高有效位的情况，我们要怎样修改形式 B 的表达式？

解答： 形式 B 的原始表达式为 \((x \ll (n+1)) - (x \ll m)\)。 当 \(n\) 是最高有效位（即 \(n = w-1\)）时，左移 \(n+1 = w\) 位在 \(w\) 位算术中相当于将所有位移出，结果为 \(0\)。 因此，形式 B 应该修改为：\(0 - (x \ll m)\)，即 \(-(x \ll m)\)。

---

练习题 2.40

题目： 对于下面每个 \(K\) 的值，找出只用指定数量的运算表达 \(x \cdot K\) 的方法。

解答：

K	移位	加法/减法	表达式
6	2	1	\((x \ll 2) + (x \ll 1)\)
31	1	1	\((x \ll 5) - x\)
-6	2	1	\((x \ll 1) - (x \ll 3)\)
55	2	2	\((x \ll 6) - (x \ll 3) - x\)

解析： 1. \(K=6\)：\(6 = 4 + 2 = 2^2 + 2^1\)。 2. \(K=31\)：\(31 = 32 - 1 = 2^5 - 2^0\)。 3. \(K=-6\)：\(-6 = 2 - 8 = 2^1 - 2^3\)。 4. \(K=55\)：\(55 = 64 - 8 - 1 = 2^6 - 2^3 - 2^0\)。

---

练习题 2.41

题目： 对于一组从位位置 \(n\) 开始到位位置 \(m\) 的连续的 \(1 (n \ge m)\)，我们看到可以产生两种形式的代码，A 和 B。编译器该如何决定使用哪一种呢？

解答： 编译器通过比较两种形式所需的运算代价来做出选择： 1. 形式 A 的表达式为 \((x \ll n) + (x \ll (n-1)) + \dots + (x \ll m)\)。它需要 \(n-m+1\) 次移位和 \(n-m\) 次加法。 2. 形式 B 的表达式为 \((x \ll (n+1)) - (x \ll m)\)。它需要 \(2\) 次移位和 \(1\) 次减法（若 \(m=0\) 则只需 \(1\) 次移位）。

决策原则： - 当 \(n=m\) 时（即只有 \(1\) 个连续的 \(1\)），形式 A 只需 \(1\) 次移位，优于形式 B。 - 当 \(n=m+1\) 时（即有 \(2\) 个连续的 \(1\)），形式 A 需要 \(2\) 次移位和 \(1\) 次加法，形式 B 需要 \(2\) 次移位和 \(1\) 次减法，两者代价相当。 - 当 \(n-m+1 > 2\) 时（即有 \(3\) 个或更多连续的 \(1\)），形式 B 所需的运算次数固定且较少，优于形式 A。 此外，如果形式 B 中的 \((x \ll (n+1))\) 涉及最高位溢出（如练习题 2.39），编译器还需要考虑负号运算的开销。总的来说，编译器会选择指令数量最少、周期总和最短的路径。

除以常数

除以 2 的幂可以通过移位运算来实现。

1. 无符号数的除法 无符号数除以 \(2^k\) 采用逻辑右移。 表达式：\(x >> k\) 结果：\(\lfloor x / 2^k \rfloor\)（向下取整）。

2. 补码（有符号数）的除法 有符号数除以 \(2^k\) 采用算术右移。但由于整数除法规则是向零舍入（Rounding toward zero），直接移位会对负数产生错误的结果（算术右移是向下取整）。

对于 \(x \ge 0\)： 直接移位即可，\(x \gg k\) 产生结果 \(\lfloor x / 2^k \rfloor\)。

对于 \(x < 0\)： 需要先加上一个偏置（Bias）量 \(2^k - 1\)，然后再执行算术右移。 表达式：\((x + (1 \ll k) - 1) \gg k\) 数学原理：利用性质 \(\lceil x / y \rceil = \lfloor (x + y - 1) / y \rfloor\)，通过加入偏置使算术右移的结果从向下取整变为向零舍入。

在 C 语言中，除以 \(2^k\) 的常用实现技巧（不使用条件判断）：

(x < 0 ? x + (1 << k) - 1 : x) >> k

或者利用符号位生成偏置：

int bias = (x >> (w - 1)) & ((1 << k) - 1);
int result = (x + bias) >> k;

练习题 2.42

题目： 写一个函数 div16，对于整数参数 x 返回 \(x / 16\) 的值。你的函数不能使用除法、模运算、乘法、任何条件语句（if 或者 ?:）、任何比较运算符（例如 <、> 或 ==）或任何循环。你可以假设数据类型 int 是 32 位长，使用补码表示，而右移是算术右移。

解答：

对于补码机器上的除法，\(x / 2^k\) 在 \(x \ge 0\) 时可以通过 \(x \gg k\) 直接计算；但在 \(x < 0\) 时，为了实现向零舍入，需要加上一个偏置（bias）\(2^k - 1\) 再右移。对于 \(16 = 2^4\)，偏置为 \(15\)。

我们需要根据 \(x\) 的符号位产生偏置：如果 \(x < 0\)，符号位为 \(1\)，算术右移 \(31\) 位得到全 \(1\)（即 \(-1\)），与 \(15\) 按位与得到 \(15\)；如果 \(x \ge 0\)，符号位为 \(0\)，算术右移 \(31\) 位得到全 \(0\)，按位与后得到 \(0\)。

int div16(int x) {
    /* 计算偏置：(x >> 31) 产生全 0 (若 x >= 0) 或全 1 (若 x < 0) */
    int bias = (x >> 31) & 0xF;
    return (x + bias) >> 4;
}

---

练习题 2.43

题目： 在下面的代码中，我们省略了常数 M 和 N 的定义。通过分析机器代码翻译回 C 语言的结果，确定 M 和 N 的值。

#define M /* Mystery number 1 */
#define N /* Mystery number 2 */
int sirith(int x, int y){
int result = 0;
result = x*M + y/N; /* M and N are mystery  numbers.*/
return result;
}

/* Translation of assembly code for arith */
int optarith(int x, int y) {
    int t = x;
    x <<= 5;
    x -= t;
    if (y < 0) y += 7;
    y >>= 3; /* Arithmetic shift */
    return x + y;
}

解答：

1. 确定 M 的值： 代码中关于 x 的操作为： \(t = x\) \(x = x \cdot 2^5 = 32x\) \(x = x - t = 32x - x = 31x\) 这对应于表达式 \(x \cdot M\)。 因此，\(M = 31\)。

2. 确定 N 的值： 代码中关于 y 的操作为： \(if (y < 0) y += 7;\) \(y \gg= 3;\) 这是对有符号整数除以 \(2^k\) 的标准优化方案。 公式为：当 \(y < 0\) 时，先加偏置 \(2^k - 1\)，再右移 \(k\) 位。 这里右移位数 \(k = 3\)，因此 \(N = 2^k = 2^3 = 8\)。 同时验证偏置：\(2^3 - 1 = 7\)，与代码中的 \(y += 7\) 完全吻合。 因此，\(N = 8\)。

总结： \(M = 31\) \(N = 8\)

浮点数表示

二进制表示浮点数有缺点，

在使用二进制小数表示浮点数时，其形式为 \(b_m b_{m-1} \dots b_0 . b_{-1} b_{-2} \dots b_{-n}\)。这种表示法的数学意义是 \(V = \sum_{i=-n}^m b_i 2^i\)。 这种方法存在明显的缺点：

1. 只能精确表示可以写作 \(x / 2^k\) 的数。其他的数值（如 \(1/3\)、\(1/5\) 或 \(1/10\)）只能近似表示，这导致简单的十进制小数在二进制中可能是无限循环的。
2. 表示极大或极小数值的效率极低。如果想表示一个非常大的数，需要大量的整数位；表示非常小的数，需要大量的小数位，这导致存储空间的巨大浪费。

所以采用 IEEE 标准的浮点表示 \[ V = (-1)^s \times M \times 2^E \] 该标准将位划分为三个字段，分别对这些参数进行编码：

1. 符号 (Sign) \(s\) 决定这个数是负数（\(s = 1\)）还是正数（\(s = 0\)）。对于数值 \(0\) 的符号位解释作为特殊情况处理。

2. 阶码 (Exponent) 字段 \(exp\) 对权重 \(E\) 进行编码。\(exp\) 是一个 \(k\) 位的无符号数，但其解释取决于浮点数的类型（是否规格化）。

3. 尾数 (Fraction) 字段 \(frac\) 对有效数 \(M\) 进行编码。\(frac\) 是一个 \(n\) 位的位向量，其解释取决于阶码字段的值是否全为 \(0\) 或全为 \(1\)。

根据 \(exp\) 字段的值，被编码的数值可以分为三种不同的情况：

1. 规格化的值 (Normalized Values) 当 \(exp\) 的位模式不全为 \(0\) 且不全为 \(1\) 时。 阶码：\(E = exp - Bias\)，其中 \(Bias = 2^{k-1} - 1\)（例如单精度时为 \(127\)）。 尾数：\(M = 1 + f\)，其中 \(f\) 是由 \(frac\) 编码的小数部分。这种方式隐含了一个开头的 \(1\)，从而获得了一个额外的精度位。

2. 非规格化的值 (Denormalized Values) 当 \(exp\) 的位模式全为 \(0\) 时。 阶码：\(E = 1 - Bias\)。 尾数：\(M = f\)，即没有隐含的 \(1\)。 用途：这种形式用于表示数值 \(0\)（当 \(frac\) 也全为 \(0\) 时），以及表示那些非常接近 \(0.0\) 的数（逐渐下溢特性）。

3. 特殊值 (Special Values) 当 \(exp\) 的位模式全为 \(1\) 时。 无穷大：当 \(frac\) 全为 \(0\) 时，表示 \(\infty\)（根据符号位分为 \(+\infty\) 和 \(-\infty\)）。 NaN (Not a Number)：当 \(frac\) 不全为 \(0\) 时。用于表示未定义的计算结果，如 \(\sqrt{-1}\) 或 \(\infty - \infty\)。

IEEE 定义了四种舍入方向：

1. 向偶数舍入 (Round-to-even)：这是默认模式，它寻找最接近的匹配值；在正好处于两个数值中间时，选择最低有效位为偶数的那一个（可以减少统计偏差）。
2. 向零舍入 (Round-toward-zero)。
3. 向下舍入 (Round-down/towards \(-\infty\))。
4. 向上舍入 (Round-up/towards \(+\infty\))。

由于这些特殊的性质，浮点数的加法不具有结合性

练习 2.53

完成下列宏定义，生成双精度值 \(+\infty\)、\(-\infty\) 和 \(0\)：

#define POS_INFINITY (1e400)
#define NEG_INFINITY (-POS_INFINITY)
#define NEG_ZERO (-0.0)

原因：由于双精度浮点数（\(double\)）能表示的最大有限值大约是 \(1.8 \times 10^{308}\)，通过定义一个远超此范围的数值（如 \(1e400\)），编译器会根据 IEEE 754 标准将其处理为正无穷大。负无穷大即为正无穷大的相反数。\(-0.0\) 是 IEEE 754 标准中定义的特殊值，可以直接通过字面量表示。

---

在 \(int\)、\(float\) 和 \(double\) 格式之间进行强制类型转换时，程序改变数值和位模式的原则如下（假设 \(int\) 是 \(32\) 位的）：

1. 从 \(int\) 转换成 \(float\)：数字不会溢出，但是可能被舍入。这是因为 \(float\) 的尾数位不足以精确表示所有 \(32\) 位整数的精度。

2. 从 \(int\) 或 \(float\) 转换成 \(double\)：由于 \(double\) 有更大的范围（即可表示值的范围），也有更高的精度（即有效位数），所以能够保留精确的数值。

3. 从 \(double\) 转换成 \(float\)：因为范围要小一些，所以值可能溢出成 \(+\infty\) 或 \(-\infty\)。另外，由于精确度较小，它还可能被舍入。

4. 从 \(float\) 或者 \(double\) 转换成 \(int\)：值将会向零舍入。例如，\(1.999\) 将被转换成 \(1\)，而 \(-1.999\) 将被转换成 \(-1\)。进一步来说，值可能会溢出。C 语言标准没有对这种情况指定固定的结果。与 Intel 兼容的微处理器指定位模式 \([10 \dots 00]\)（字长为 \(w\) 时的 \(TMin_w\)）为整数不确定（integer indefinite）值。一个从浮点数到整数的转换，如果不能为该浮点数找到一个合理的整数近似值，就会产生这样一个值。因此，表达式 \((int)+1e10\) 会得到 \(-21483648\)，即从一个正值变成了一个负值。

#define POS_INFINITY (1e400)
#define NEG_INFINITY (-POS_INFINITY)
#define NEG_ZERO     (-0.0)

练习 2.54

说明：假设 \(x\) 为 \(int\) 类型，\(f\) 为 \(float\) 类型，\(d\) 为 \(double\) 类型。在采用 IEEE 754 浮点标准的 32 位机器上，判定下列每个表达式是否始终为真（True）或可能为假（False）。如果为假，请给出反例或解释原因。

A. \(x == (int)(double) x\) 解答：始终为真（True）。 原因：\(double\) 类型的尾数位（\(53\) 位）远大于 \(int\) 类型的位数（\(31\) 位数值位），因此 \(int\) 转换为 \(double\) 不会丢失任何精度。将该 \(double\) 值转回 \(int\) 时，数值保持不变。

B. \(x == (int)(float) x\) 解答：可能为假（False）。 原因：\(float\) 类型的尾数位只有 \(24\) 位。当 \(int\) 超过 \(2^24\) 且低位不为 \(0\) 时（例如 \(x = 2^{24} + 1\)），转换为 \(float\) 会发生舍入，导致信息丢失。

C. \(d == (double)(float) d\) 解答：可能为假（False）。 原因：\(float\) 的表示范围和精度都远小于 \(double\)。如果 \(d\) 的值非常大（例如 \(1e40\)），转换为 \(float\) 会溢出为 \(+\infty\)；或者如果 \(d\) 的精度超出了 \(24\) 位尾数的范围，转换也会丢失精度。

D. \(f == (float)(double) f\) 解答：始终为真（True）。 原因：\(float\) 转换为 \(double\) 是完全精确的扩充。将更高精度的 \(double\) 转回 \(float\) 时，会得到原始的 \(float\) 值。

E. \(f == -(-f)\) 解答：始终为真（True）。 原因：浮点数的取反操作仅仅是改变符号位的值，两次取反必然回到原始状态。

F. \(1.0/2 == 1/2.0\) 解答：始终为真（True）。 原因：在 C 语言中，如果除法运算中有一个操作数是浮点数，另一个操作数也会被提升为同类型的浮点数。两侧都会执行 \(1.0 / 2.0\) 的双精度浮点除法，结果均为 \(0.5\)。

G. \(d \cdot d \ge 0.0\) 解答：可能为假（False）。 原因：如果 \(d\) 是特殊值 \(NaN\)（非数），根据 IEEE 754 标准，任何涉及 \(NaN\) 的比较运算（除了 \(!=\)）结果都为假。即使是 \(NaN \ge 0.0\) 也会返回 \(False\)。

H. \((f+d)-f == d\) 解答：可能为假（False）。 原因：浮点数加法不满足结合律。如果 \(f\) 的数值极大而 \(d\) 极小（例如 \(f = 1e20, d = 1.0\)），\(f + d\) 的结果由于精度限制可能仍然等于 \(f\)。此时 \((f + d) - f\) 的结果为 \(0.0\)，不等于 \(1.0\)。

I. \((int)(double) d == d\) 解答：可能为假（False）。 原因：如果 \(d\) 具有小数部分（如 \(0.5\)），强制转换为 \(int\) 会导致截断（变为 \(0\)），数值发生改变。另外，\(d\) 如果超出 \(int\) 的表示范围（如 \(1e20\)），转换结果也会不确定。

J. \(f > -f\) 解答：可能为假（False）。 原因：如果 \(f = 0.0\)（包括 \(+0.0\) 或 \(-0.0\)），则 \(f > -f\) 的结果为假。此外，如果 \(f = NaN\)，比较结果也为假。

家庭作业

Amdahl 定律相关习题

补充1

计算机系统中有三个部件可以改进，这三个部件的部件加速比如下：部件加速比1=30，部件加速比2=20，部件加速比3=10。如果相对某个测试程序三个部件的所需执行时间与总时间的比例分别为10%，20%和70%，要达到最好改进效果，仅对一个部件改进时，要选择哪个部件？如果允许改进两个部件，又如何选择?

\(S_=\frac{1}{(1-\alpha_1)+\alpha_1/k_1}\) 约为 1.107

\(S_2=\frac{1}{(1-\alpha_2)+\alpha_2/k_2}\) 约为 1.235

\(S_3=\frac{1}{(1-\alpha_3)+\alpha_3/k_3}\) 约为 2.473

选择部件三

如果允许改进两个部件，选择部件二和部件三。

可以通过下面这个公式计算

\(S_{ij}=\frac{1}{(1-\alpha_i-\alpha_j)+\alpha_i/k_i+\alpha_j/k_j}\)

2.58

int is_little_endian() {
    unsigned int x = 1;
    char *c = (char*)&x;
    return *c;
}

2.59

int fun(int x, int y){
	int mask = 0xFF;
    return (x & mask) | (y & ~mask);
}

2.60

unsigned replace_byte(unsigned x, int i, unsigned char b) {
    unsigned mask = 0xFF << (i << 3);
    unsigned b_shifted = (unsigned)b << (i << 3);
    return (x & ~mask) | b_shifted;
}

2.61

A.!(~x)

B.!x

C.!(x&0xFF)

D.!(x>>(sizeof(int) - 1 ) << 3

2.62

int int_shift_are_arithmetic(){
    int x=-1;
    return x == x >> 3;
}

2.63

unsigned srl(unsigned x, int k) {
    unsigned xsra = (int)x >> k;
    int w = sizeof(int) << 3;
    unsigned mask = (1 << (w - k)) - 1;
    return xsra & mask;
}

int sra(int x, int k) {
    int xsrl = (unsigned)x >> k;
    int w = sizeof(int) << 3;
    unsigned mask = (1 << (w - k)) - 1;
    return xsrl | (~mask);
}

2.64

int any_odd_one(unsigned x) {
    x = x | (x >> 16);
    x = x | (x >> 8);
    x = x | (x >> 4);
    x = x | (x >> 2);
    x = x | (x >> 1);
    return x & 1;
}

2.65

int odd_ones(unsigned x) {
    x = x ^ (x >> 16);
    x = x ^ (x >> 8);
    x = x ^ (x >> 4);
    x = x ^ (x >> 2);
    x = x ^ (x >> 1);
    return x & 1;
}

2.66

int leftmost_one(unsigned x) {
    if (x == 0) return 0;
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x & ~(x >> 1);
}

2.67

32 位机器最多只能移动 31 位

int int_size_is_32() {
    int set_msb = 1 << 31;
    int beyond_msb = set_msb << 1;
    return set_msb && !beyond_msb;
}

int inr_size_is_16(){
    short set_msb = 1 << 15;
    short beyond_msb = set_msb << 1;
    return set_msb && !beyond_msb;
}

2.68

int lower_one_mask(int n) {
    int w = sizeof(int) << 3;
    return -1U >> (w - n);
}

2.69

unsigned rotate_left(unsigned x, int n) {
    int w = sizeof(int) << 3;
    unsigned left_shifted = x << n;
    unsigned right_shifted = x >> (w - n);
    return left_shifted | right_shifted;
}

2.70

int fits_bits(int x, int n) {
    int w = sizeof(int) << 3;
    int shift = w - n;    
    return (x << shift >> shift) == x; 
}

2.71

由于 word 是无符号类型，右移时高位补 0，因此无法正确判断负数

inr xbyte(int x, int i) {
    return (x >> (i << 3)) & 0xFF;
}

2.72

A. 因为结果无符号

if(maxbyte > sizeof(val))

2.73

int saturating_add(int x, int y) {
    int sum = x + y;
    int sig_mask = INT_MIN;
    
    int pos_over = ~(x & sig_mask) & ~(y & sig_mask) & (sum & sig_mask);
    int neg_over = (x & sig_mask) & (y & sig_mask) &    ~(sum & sig_mask); 
    pos_over && (sum = INT_MAX);
    neg_over && (sum = INT_MIN);    
    return sum;
}

2.74

int tsub_ok(int x, int y) {
	    int diff = x - y;
    int sig_mask = INT_MIN;

    int pos_over = ~(x & sig_mask) & (y & sig_mask) & (diff & sig_mask);
    int neg_over = (x & sig_mask) & ~(y & sig_mask) & ~(diff & sig_mask); 
    return !pos_over && !neg_over;
}

2.75

int signed_high_prod(int x, int y) {
    int64_t p = (int64_t)x * (int64_t)y;
    return (int)(p >> 32);
}
int unsigned_high_prod(unsigned x, unsigned y) {
    int bit_x = x >> 31;
    int bit_y = y >> 31;    
    int sig_prod = signed_high_prod((int)x, (int)y);
    return sign_prod + x * bit_y + y * bit_x;
}

2.76

void *calloc(size_t nmeb, size_t size) {
    size_t total_size = nmeb * size;
    void *ptr = malloc(total_size);
    if (ptr) {
        memset(ptr, 0, total_size);
    }
    return ptr;
}

2.77

x << 4 + x

x - (x << 3)

(x << 6) - (x << 2)

(x << 4) - (x << 7)

2.78

int divide_power2(int x, int k){
    int bias = (x >> 31) & ((1 << k) - 1);    
    return (x + bias) >> k;

}

2.79

int mul3div4(int x) {
    int mul3 = (x << 1) + x; 
    int bias = (mul3 >> 31) & 3; 
    return (mul3 + bias) >> 2;
}

2.80

int threefourths(int x) {
    int bias = (x >> 31) & 3;
    x = (x + bias) >> 2;
    return (x << 1) + x;    
}

2.81

-1 << k

~(-1 << k) ^ (-1 << j))

2.82

A.错误

INT_MIN 的取反加一仍为 INT_MIN

BCDE 正确

2.83

A. \(\frac{Y}{2^k-1}\)

1. \(\frac{5}{7}\)

2. \(\frac{2}{5}\)

3. \(\frac{19}{63}\)

2.84

inr float_le(float x, float y){
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);    
    unsigned sign_x = ux >> 31;
    unsigned sign_y = uy >> 31;
    return !(ux << 1 || uy << 1) || 
        (sign_x && !sign_y) || 
        (!(sign_x ^ sign_y) &&
         (ux <= uy));
}

2.85

\(7.0 = (-1)^s \times M \times 2^E\)

\(s = 0\)

\(E = 2\)

\(M = 1.75 = 1 + 0.75 = 1 + \frac{3}{4} = 1 + 2^{-1} + 2^{-2}\)

\(bias = 2^{k-1}-1\)

\(exp = E + bias = 2 + bias\)

最大奇整数

\(M\) 要是最大，全部 \(1\)

由于是整数，为了使得 \(M\) 最大，\(E\) 要取 \(n\)

此时值为 \(2^{n+1}-1\)

最小规格化数 \(M\) 取 \(1\)

\(E\) 取最小值 \(1 - bias= 2^{k-1}-2\)

值为 \(2^{1-bias} = 2^{2^{k-1}-2}\)

2.86

最小正非规格化数

阶码 \(exp\) 全零， \(E\)= 1-\(bias\)，尾数 \(frac\) 只有最低位为 \(1\)

值为 \(2^{1-bias} \times 2^{-n} = 2^{-bias-n+1}\)

最小正规格化数

阶码 \(exp\) 为 \(1\)，\(E\)= 1-\(bias\)，尾数 \(frac\) 全零

值为 \(2^{1-bias}\)

最大规格化数

阶码 \(exp\) 全为 \(1\) 除了最低位为 \(0\)，\(E\)= \(bias\)，尾数 \(frac\) 全为 \(1\)

值为 \((2 - 2^{-n}) \times 2^{bias} = 2^{bias+1} - 2^{bias-n+1}\)

2.87

描述	Hex	M	E	V	D
-0	8000	0	0	-0	-0.0
最小的 \(>2\) 的值	4001	\(1+2^{-10}\)	1	\(2*(1+2^{-10})\)	2.00195
512	6000	1	9	512	512.0
最大的非规格化数	03ff	\(1-2^{-10}\)	-14	\((1-2^{-10})*2^{-14}\)	0.000061
\(-\infty\)	fc00	–	–	\(-\infty\)	\(-\infty\)
十六进制表示为 3BB0 的数	3BB0	\(\frac{123}{64}\)	-1	\(\frac{123}{128}\)	0.961

2.88

位	值	位	值
1 01110 001	-9/16	1 0110 0010	-9/16
0 10110 101	208	0 1110 1010	208
1 00111 110	-7/1024	1 0000 0111	-7/1024
0 00000 101	2^(-14) * 5/8	0 0000 0001	1/1024
1 11011 000	-2^12	1 1110 1111	-248
0 11000 100	768	0 1111 0000	+ ∞

2.89

正确

错误，y为INT_MIN 溢出

因为它的位是由int随机生成的，转化为double仍在double能精确表示的范围内

所以满足结合律

正确

错误

都大时，超出最大表示范围

错误

可能为0