CSAPP 第二章：信息的表示和处理

2.1 信息存储

位和字节

计算机中最小的存储单位是位（bit），每个位可以存储0或1。
8个位构成一个字节（byte），通常用于表示一个字符或一个整数的值。
计算机中的数据是按字节为单位存储的，每个字节都有一个唯一的地址。

十六进制表示法

十六进制表示法用于方便地表示二进制数。
每个十六进制数字对应于4个二进制位，因此一个字节可以表示为两个十六进制数字。
十六进制数字包括0到9和A到F。

字数据大小

计算机中常用的字大小有1字节（8位）、2字节（16位）、4字节（32位）和8字节（64位）。
不同的字大小可以表示的最大值不同，例如1字节可以表示的最大值为255（\(2^8-1\)），而4字节可以表示的最大值为4294967295（\(2^{32}-1\)）。

数据类型

不同类型的数据在计算机中存储的方式不同。
布尔类型通常存储为1字节，0表示假，非0表示真。
整数类型可以使用有符号或无符号表示，有符号类型使用补码表示，无符号类型使用无符号整数表示。
浮点数类型通常使用IEEE标准表示，包括符号位、指数位和尾数位。

C语言数据类型

C语言支持各种数据类型，包括整数类型、浮点数类型、字符类型等。不同的数据类型在内存中占用的字节数不同，可以使用sizeof运算符获取。
在C语言中，常量可以直接使用字面值表示，例如整数常量、浮点数常量、字符常量等。
为什么防止不同编译器的不同设置引起的奇怪问题，引入了数据大小固定的数据类型，例如int32_t和int64_t。

大端和小端

在计算机中，数据在内存中存储时需要占用多个字节。大端和小端是两种不同的字节序，用于确定多字节数据中字节的存储顺序。

大端字节序：在大端字节序中，最高位字节（即最高有效字节）存储在最低地址处，最低位字节（即最低有效字节）存储在最高地址处。例如，十六进制数0x12345678在大端字节序中存储为12 34 56 78，最高位字节0x12存储在最低地址处，最低位字节0x78存储在最高地址处。
小端字节序：在小端字节序中，最低位字节（即最低有效字节）存储在最低地址处，最高位字节（即最高有效字节）存储在最高地址处。例如，十六进制数0x12345678在小端字节序中存储为78 56 34 12，最低位字节0x78存储在最低地址处，最高位字节0x12存储在最高地址处。

两种字节序的区别在于多字节数据的字节存储顺序，而单字节数据的字节存储顺序是相同的。在网络通信和数据传输中，通常使用大端字节序。一些计算机处理器（如PowerPC）采用大端字节序，而另一些计算机处理器（如x86）采用小端字节序。在程序开发中，需要考虑字节序的问题，以免造成数据解析错误或不兼容的问题。

布尔代数

布尔代数是一种数学分支，也是一种逻辑代数。它以二元关系和二元运算为基础，用于描述逻辑命题和逻辑运算，其中的基本元素只有两个值，通常用0和1表示。在布尔代数中，0表示假，1表示真。

布尔代数的运算包括与（AND）、或（OR）、非（NOT）和异或（XOR）等。以AND运算为例，当两个元素的值均为1时，AND运算的结果为1，否则为0。OR运算的结果是两个元素的值中至少有一个为1时为1，否则为0。NOT运算的结果是一个元素的值取反，即1变成0，0变成1。XOR运算的结果是两个元素的值不相同时为1，相同时为0。

利用异或的性质解题：leetcode-136. 只出现一次的数字

布尔代数广泛应用于计算机科学领域中的逻辑设计、编译器设计、数据结构、算法设计等方面。例如，在逻辑电路的设计中，可以使用布尔代数的公式来简化电路的设计，从而减少电路的复杂性和成本。在编译器的设计中，布尔代数也被用来描述和优化中间代码和目标代码的生成和优化过程。在数据结构和算法设计中，布尔代数常常被用来描述逻辑运算和条件判断等。

C语言中的逻辑运算

逻辑与（&&）运算符表示两个表达式都为真时结果为真，只要有一个表达式为假则结果为假。例如，a && b表示当a和b都为真时结果为真，否则结果为假。

逻辑或（||）运算符表示两个表达式有一个为真时结果为真，只有两个表达式都为假时结果为假。例如，a || b表示当a或b中有一个为真时结果为真，否则结果为假。

逻辑非（!）运算符表示对一个表达式取反。例如，!a表示当a为假时结果为真，当a为真时结果为假。

C语言中的移位

C语言中的移位运算是位运算的一种，包括左移运算符（<<）、逻辑右移运算符（>>>）、算术右移运算符（>>）。

左移运算符（<<）将一个数的二进制表示向左移动指定的位数，右侧空出的位补0。例如，a << 2表示将a的二进制表示向左移动2位，即将a的值乘以4。

逻辑右移运算符（>>>）将一个数的二进制表示向右移动指定的位数，左侧空出的位补0。例如，a >>> 1表示将a的二进制表示向右移动1位，左侧空出的位补0。

算术右移运算符（>>）将一个数的二进制表示向右移动指定的位数，左侧空出的位补符号位，即正数补0，负数补1。例如，a >> 1表示将a的二进制表示向右移动1位，即将a的值除以2。

在C语言标准中，并没有明确定义算术右移和逻辑右移的方法，具体的实现方式取决于编译器和处理器的实现。在实际中，大部分的处理器都采用了算术右移的方式来进行有符号数的右移操作，即将左侧空出的位补上符号位；而无符号数的右移操作一般采用逻辑右移的方式，即左侧空出的位补0。

由于C语言标准并没有规定右移的行为，因此在进行有符号数的右移操作时，存在一些跨平台的兼容性问题，不同的编译器和处理器可能会有不同的实现方式。因此，为了避免这些问题，建议在进行右移操作时，尽量使用无符号数进行位运算，或者使用移位后进行符号扩展的方法。

移位运算在C语言中常用于优化计算，比如将乘法运算转化为移位运算。需要注意的是，移位运算符的使用需要遵循一定的规则，如不可将一个数向右移动超过它的位数，否则结果将不可预知。在使用算术右移时，需要注意负数的符号扩展问题，可以通过逻辑右移再进行符号位的处理。

2.2 整数表示

补码

补码是一种用来表示有符号整数的编码方式。对于一个n位二进制数，它的补码表示方法如下：

对于正数，它的补码就是它的原码（即二进制数的绝对值）
对于负数，它的补码是将它的原码除符号位以外的所有位按位取反，然后再加1所得到的结果

对于一个n位的补码数X，其数值表示为：

\[ X = -w_{n-1} × 2^{n-1} + ∑_{i=0}^{n-2}w_i × 2^i \]

其中，\(w_{n-1}\)表示符号位，若为0则表示正数，若为1则表示负数。

以一个8位的有符号整数-7为例，其原码为：

\[ -7_{10} = 10000111_{2} \]

将其转换为补码：

对于符号位，符号位为1，表示负数。
对于除符号位以外的所有位，将其取反得到01111000。
将取反后的结果加1，得到01111001。

因此，-7的补码表示为01111001。

有符号数和无符号数的运算与转化

有符号数和无符号数的运算和转化涉及到它们在内存中存储的方式不同，可能会导致意想不到的结果。

首先，无符号数的取值范围是 \(0\) 到 \(2^n-1\)，其中 \(n\) 是该类型的位数。因此，当无符号数的值为 \(0\) 时，其所有位都为 \(0\)。

而对于有符号数，它的第一位通常表示它的符号。使用补码表示时，有符号数的取值范围是 \(-2^{n-1}\) 到 \(2^{n-1}-1\)。对于一个 \(n\) 位的有符号数，最高位的权重是 \(-2^{n-1}\)，其余位的权重分别为 \(2^{n-2}\)、\(2^{n-3}\)、\(\cdots\)、\(2^0\)。

当有符号数和无符号数发生运算时，C语言会将无符号数当作有符号数进行运算。如果无符号数的值小于 \(0\)，那么它会被解释为有符号数的一个较大的正数值，这可能导致意想不到的结果。

当将有符号数转换为无符号数时，如果该数的值为负，则将其值加上 \(2^n\)（其中 \(n\) 是该类型的位数），直到它成为一个非负数。这种转换也可能导致意想不到的结果，例如：

1
2
3

unsigned int x = 10;
int y = -20;
printf("%u\n", x + y);

上面的代码中，y 被转换为一个无符号数，其值为 \(2^{32}-20\)。因此，x + y 的值为 \(2^{32}-10\)，它通常不是我们想要的结果。

拓展与截断

拓展和截断是指对于一个数据类型，将其从一种宽度（width）转换为另一种宽度的过程。

拓展指将一个较窄的数据类型转换为一个较宽的数据类型时所进行的操作。例如，将一个8位的无符号数拓展为一个16位的无符号数，就需要将其高位补0。拓展操作可以通过左移、右移和或操作等方式来实现。

例如，将一个8位的无符号数x拓展为一个16位的无符号数y，可以使用下面的代码：

1 2	unsigned char x = 0x23; // 0000 0010 unsigned short y = (unsigned short) x; // 0000 0000 0010 0011

在上面的代码中，我们将x拓展为一个16位的无符号数y，使用了显式类型转换的方式。

截断指将一个较宽的数据类型转换为一个较窄的数据类型时所进行的操作。例如，将一个32位的整数截断为一个16位的整数，就需要将其高位截断。截断操作会导致数据的精度降低，可能会导致精度损失和数据溢出等问题。

例如，将一个32位的有符号整数x截断为一个16位的有符号整数y，可以使用下面的代码：

1 2	int x = 0x0000ffff; // 0000 0000 0000 0000 1111 1111 1111 1111 short y = (short) x; // 1111 1111 1111 1111

在上面的代码中，我们将x截断为一个16位的有符号整数y，使用了显式类型转换的方式。由于x的高位都是0，因此截断的结果和原始值相同。

需要注意的是，对于有符号整数的拓展和截断操作，其具体的结果取决于CPU的架构和编译器的实现。例如，对于有符号整数的截断操作，一些编译器会采用“截断高位，保留低位”的方式，而另一些编译器则会采用“截断低位，保留符号位”的方式。因此，在进行数据类型转换时，应该根据具体的编译器和CPU架构来决定具体的实现方式。

2.3 整数运算

无符号数加法

在无符号数加法中，操作数被当做没有符号的正数进行处理。无符号数加法遵循模算术（模为 2 的 n 次方，n 是数的位数），当结果超出模范围时，结果会对模取模，保留余数。例如，8 位无符号数的模为 256，当两个 8 位无符号数相加时，如果结果大于 255，则结果会对 256 取模，例如：

1	200 + 100 = 44 (mod 256)

补码加法

补码加法则是一种计算机中常用的有符号数加法方式。在补码表示中，正数的补码和无符号数的表示相同，而负数的补码是将其对应正数的二进制表示取反后加 1 所得到的二进制数。补码加法与无符号数加法的区别在于，补码加法中，数的范围是从 \(-2^{n-1}\) 到 \(2^{n-1}-1\)，其中 n 是数的位数。在补码加法中，如果两个数的和超出了这个范围，则会发生溢出。

在补码加法中，当两个数相加时，如果最高位进位了，就会导致溢出，此时计算机会将结果的最高位截断并将其存储在进位标志寄存器中，以便程序员检测是否发生了溢出。

有符号数的溢出

对于有符号数，溢出有以下两种情况：

正数加正数得到负数，或者负数加负数得到正数。这种情况被称为“符号位溢出”，因为结果的符号与输入操作数的符号不同。这种溢出通常是由于操作数的符号位的进位或借位错误造成的。

两个正数相加得到一个大于等于最大正数，或者两个负数相加得到一个小于等于最小负数。这种情况被称为“数值位溢出”，因为结果的绝对值超出了有符号数的表示范围。这种溢出通常是由于两个操作数的绝对值相加超出了数据类型的范围造成的。

处理这些溢出的方法如下：

符号位溢出：可以通过在操作数的高位添加一位来检测符号位溢出。当符号位和进位不同时，就发生了符号位溢出。处理符号位溢出的方法包括检查符号位和进位是否相同，并相应地修改结果的符号位。

数值位溢出：可以通过比较加法的操作数和结果的符号位来检测数值位溢出。如果操作数的符号位相同，但结果的符号位与它们不同，则发生了数值位溢出。处理数值位溢出的方法包括将操作数和结果向上或向下舍入，或者将结果截断为最大或最小值。

在实际应用中，为了避免这些溢出，通常需要进行数据类型检查和数据范围限制，以确保操作数不会超出数据类型的表示范围。此外，在编写代码时，应该尽可能地避免使用可能导致溢出的算术运算。

无符号乘法

无符号乘法是指对两个无符号整数进行乘法运算，得到的结果也是一个无符号整数。在无符号乘法中，计算机将两个数按位相乘，然后再将结果相加得到最终的乘积。由于无符号整数没有正负之分，因此无符号乘法不需要考虑进位或溢出的问题。

可以简单地表示无符号乘法的公式如下：

\[ C = A * B mod 2^ω \]

补码乘法

对无符号和补码乘法，乘法运算的位级表示都是一样的。
机器使用一种乘法指令来进行有符号和无符号整数的乘法，也就是都采用无符号乘法处理，再取低位。
无符号和补码的乘法低位是相同的。证明如下：

补码乘法的过程主要包括三个步骤：补码表示、乘法运算和结果转换。

下面是补码乘法的详细步骤：

将两个乘数转换为它们的补码形式。如果乘数是正数，则它们的补码与原码相同；如果乘数是负数，则需要将它们的绝对值转换为二进制补码形式，并将符号位取反，然后再将符号位和数值位组合起来得到补码。
将两个补码乘起来，得到一个结果的补码。在这个过程中，可以使用常规的乘法算法，将乘数逐位与被乘数相乘，并将结果相加。需要注意的是，结果的位数可能会超过原始数的位数，需要进行适当的位扩展。
将结果的补码转换为原码。如果结果是正数，则它们的补码与原码相同；如果结果是负数，则需要将它们的绝对值转换为二进制补码形式，并将符号位取反，然后再将符号位和数值位组合起来得到原码。

举例说明补码乘法：

          1111 1111        -1
       x  1111 1001     x  -7
      ----------------    ------
          11111111          7
         00000000
        00000000
       11111111
      11111111
     11111111
    11111111
   11111111
   ----------------
1  00000000111       --->  7 (notice the Most significant bit is zero)
(last 8-bits needed)

乘以常数

把一个数乘以\(2^n\),相当于左移n位。

整数乘法运算在大多数机器上都相当慢（10个或者更多的时钟周期），而其他整数运算（加法、减法、位运算和移位）只需要一个时钟周期。

因此许多C语言编译器识图用移位、加法和减法的组合来代替乘法。

例如表达式\(x*14=x<<3+x<<2+x<<1\)，当然更好的办法是\(x*14=x<<4-x<<1\)。

除以2的幂

同样地，我们可以用分别用逻辑右移和算术右移代替无符号数和补码的除以2的幂的除法。

逻辑右移的情况下，不需要任何额外的操作。

但是在算术右移的时候，会出现向下取整的情况。当结果是负数的时候，就会出现不合适的舍入。这时候，我们就应该先加上一个偏置值(\(2^k - 1\))，再进行移位。

测试题：在不使用任何乘除法、模运算、条件语句、比较运算符、循环的情况下，写一个函数，返回整数参数\(x/16\)的值。

int div16(int x){
   int bias = (x >> 31) &0XF;
   return (x + bias) >> 4;
}

2.4 浮点数

现实的应用中，需要表示一些非常大的数字或者非常接近0的数字，以及更普遍地作为实数运算的近似值的计算，这是就需要浮点数的表示。

其中IEEE754标准定义的浮点数规则，广泛地被应用。

二进制小数

在二进制中，不同位置的数字带有\(2^n\)的权，基于同样的原则，我们也能推广到负位置上，不同位置上的数字，也可以代表\(\frac{1}{2}、\frac{1}{4}\)等等。

这样的表示方法，就带来一个问题：用有限位数的二进制数表示十进制小数，只能近似地表示（当然，增加二进制数的表示长度，可以提升近似地精度）。

IEEE浮点表示

IEEE 754是一种常用的标准。它定义了浮点数的表示方法和运算规则。

浮点数的组成部分

IEEE 754浮点数由三个主要部分组成：符号位（Sign）、指数位（Exponent）和尾数位（Significand/Mantissa）。每个部分在浮点数的二进制表示中具有特定的意义。

符号位（Sign）：用于表示浮点数的正负号。0表示正数，1表示负数。
指数位（Exponent）：表示浮点数的指数部分，用于确定浮点数的数量级。指数位的值采用偏移表示法（移码），其中偏移值为2^(n-1) - 1，其中n是指数位的位数。
尾数位（Significand/Mantissa）：表示浮点数的小数部分。尾数位决定了浮点数的精度。

在单精度浮点数中，三个部分分别占1、8、23位，而在双精度浮点数中，三个部分分别占1、11、52位。

规格化与非规格化

规格化值（Normalized Value）：如果浮点数中指数部分的编码值既不是全0，又不是全1，且在科学表示法的表示方式下，分数 (fraction) 部分最高有效位（即整数字）是1，那么这个浮点数将被称为规约形式的浮点数。“规约”是指用唯一确定的浮点形式去表示一个值。由于这种表示下的尾数有一位隐含的二进制有效数字，为了与二进制科学计数法的尾数（mantissa）相区别，IEEE754称之为有效数（significant）。
非规格化值（Denormalized Value）：如果浮点数的指数部分的编码值是0，分数部分非零，那么这个浮点数将被称为非规约形式的浮点数。一般是某个数字相当接近零时才会使用非规约型式来表示。 IEEE 754标准规定：非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值小1。例如，最小的规约形式的单精度浮点数的指数部分编码值为1，指数的实际值为-126；而非规约的单精度浮点数的指数域编码值为0，对应的指数实际值也是-126而不是-127。实际上非规约形式的浮点数仍然是有效可以使用的，只是它们的绝对值已经小于所有的规约浮点数的绝对值；即所有的非规约浮点数比规约浮点数更接近0。规约浮点数的尾数大于等于1且小于2，而非规约浮点数的尾数小于1且大于0。

特殊值

三个特殊值需要指出：

如果指数是0并且尾数的小数部分是0，这个数±0（和符号位相关）
如果指数为\(2^e-1\)并且尾数的小数部分是0，这个数是±∞（同样和符号位相关）
如果指数为\(2^e-1\)并且尾数的小数部分非0，这个数表示为非数（NaN）。

总结

总结以上所有的情况：

形式	指数	小数部分
零	0	0
非规约形式	0	大于0小于1
规约形式	1到2^(e)-2	大于等于1小于2
无穷	2^(e)-1	0
NaN	2^(e)-1	非0

单精度浮点数各种极值情况：

类别	正负号	实际指数	有偏移指数	指数域	尾数域	数值
零	0	-127	0	0000 0000	000 0000 0000 0000 0000 0000	0.0
负零	1	-127	0	0000 0000	000 0000 0000 0000 0000 0000	-0.0
1	0	0	127	0111 1111	000 0000 0000 0000 0000 0000	1.0
-1	1	0	127	0111 1111	000 0000 0000 0000 0000 0000	-1.0
最小的非规约数	*	-126	0	0000 0000	000 0000 0000 0000 0000 0001	±2^-23 × 2^-126 ≈ ±2^-149 ≈ ±1.4×10^-45
中间大小的非规约数	*	-126	0	0000 0000	100 0000 0000 0000 0000 0000	±2^-1 × 2^-126 ≈ ±2^-127 ≈ ±5.88×10^-39
最大的非规约数	*	-126	0	0000 0000	111 1111 1111 1111 1111 1111	±(1-2^-23) × 2^-126 ≈ ±1.18×10^-38
最小的规约数	*	-126	1	0000 0001	000 0000 0000 0000 0000 0000	±2^-126 ≈ ±1.18×10^-38
最大的规约数	*	127	254	1111 1110	111 1111 1111 1111 1111 1111	±(2^-2-23) × 2^127 ≈ ±3.4×10^38
正无穷	0	128	255	1111 1111	000 0000 0000 0000 0000 0000	+∞
负无穷	1	128	255	1111 1111	000 0000 0000 0000 0000 0000	-∞
NaN	*	128	255	1111 1111	非全0	NaN

浮点数的舍入

任何有效数上的运算结果，通常都存放在较长的寄存器中，当结果被放回浮点格式时，必须将多出来的比特丢弃。有多种方法可以用来执行舍入作业，实际上IEEE标准列出4种不同的方法：

舍入到最接近：舍入到最接近，在一样接近的情况下偶数优先（Ties To Even，这是默认的舍入方式）：会将结果舍入为最接近且可以表示的值，但是当存在两个数一样接近的时候，则取其中的偶数（在二进制中是以0结尾的）。
朝+∞方向舍入：会将结果朝正无限大的方向舍入。
朝-∞方向舍入：会将结果朝负无限大的方向舍入。
朝0方向舍入：会将结果朝0的方向舍入。

浮点数的运算性质

浮点数的运算不遵循结合性和分配性。