CSAPP-信息的表示和处理

人总是对记忆有一种放不下的假清高，渴望在过去里找一点存在感，却因此而陷入更深的纠结。这并不能减少人的迷茫彷徨，反而会加剧内心的动荡。
理解和接受过去的自己，这很重要。同时也要带着乐观派、理想主义和克制活着。
—— 2023.10.31记。

信息存储

大多数计算机使用 8 位的块，或者字节作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存(virtual memory)。内存的每个字节都由一个唯一的数字来标识，称为它的地址(address)，所有可能地址的集合就称为虚拟地址空间(virtual address space)。

• 无符号编码基于传统的二进制表示法，表示大于或者等于零的数字;
• 补码(two’s-complement) 编码是表示有符号整数的最常见的方式;
• 移码(增码) 是符号位取反的补码，一般用指数的移码减去1来做浮点数的阶码，引入的目的是为了保证浮点数的机器零为全0;
• 原码(true form) 是一种计算机中对数字的二进制定点表示方法。原码表示法在数值前面增加了一位符号位(即最高位为符号位):正数该位为0，负数该位为1(0有两种表示:+0和-0)，其余位表示数值的大小;
• 浮点数(floating-point) 编码是表示实数的科学计数法的以2为基数的版本。

十六进制(hex)

使用 $0\sim 9$ 和 $A\sim F$ 来表示 0000 到 1111 ，在 C 语言中，以 0x 或 0X 开头的数字常量通常被认为是十六进制的值，字符 $A\sim F$ 可以是大写也可以是小写，也可以大小写混合。将一个二进制的数转换为十六进制需要将该数划分为每4个为一组，如果不是4的倍数则在最左边补0

而十进制转换为十六进制的话，可以使用辗转相除法，即不断除以16得到余数，再从下往上取。例如

$$\begin{align*} 314156 &= 19634 \times 16 + 12 \tag{C}\\ 19634 &= 1227\times 16+2 \tag{2}\\ 1227 &= 76\times 16+11 \tag{B}\\ 76 &= 4\times 16 + 12 \tag{C}\\ 4 &= 0\times 16 + 4 \tag{4} \end{align*}$$

所以 314156 的十六进制表示就是 0x4CB2C 。反过来，将16进制转换为10进制只需要不断乘上16的幂次相加即可，例如 $314156 = 4\times 16^4 + 12\times 16^3 + 11\times 16^2 + 2\times 16^1 + 12$ .

字数据大小

每台计算机都有一个字长(word size)，指明指针数据的标称大小(nominal size)，字长决定了虚拟地址空间的最大大小: 对于一台字长为 $\omega$ 位的机器，虚拟地址的范围为 $0\sim 2^{\omega}-1$

寻址和字节顺序

基本上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

排列表示一个对象的字节有两个通用的规则:

• 小端法(little ending): 最低有效字节在前面的方式(低位放在低地址)
• 大端法(big ending): 最高有效字节在前面(高位放在低地址)

CSAPP里关于大小端之争记录的一个有趣故事: “ ‘……我下面要告诉你的是， Lilliput 和 Blefuscu 这两大强国在过去 36 个月里一直在苦战。战争开始是由于以下的原因：我们大家都认为，吃鸡蛋前，原始的方法是打破鸡蛋较大的一端，可是当今皇帝的祖父小时候吃鸡蛋，一次按古法打鸡蛋时碰巧将一个手指弄破了，因此他的父亲，当时的皇帝，就下了一道敕令，命令全体臣民吃鸡蛋时打破鸡蛋较小的一端，违令者重罚。老百姓们对这项命令极为反感。历史告诉我们，由此曾发生过六次叛乱，其中一个皇帝送了命，另一个丢了王位。这些叛乱大多都是由 Ble­fuscu 的国王大臣们煽动起来的。叛乱平息后，流亡的人总是逃到那个帝国去寻救避难。据估计，先后几次有 11000 人情愿受死也不肯去打破鸡蛋较小的一端。关于这一争端，曾出版过几百本大部著作，不过大端派的书一直是受禁的，法律也规定该派的任何人不得做官。’(此段译文摘自网上蒋剑锋译的 《 格利佛游记 》 第一卷第 4 章。)
在他那个时代，Swift 是在讽刺英国(Lilliput)和法国(Blefuscu)之间持续的冲突。Danny Cohen, 一位网络协议的早期开创者，第一次使用这两个术语来指代字节顺序, 后来这个术语被广泛接纳了 。“

字符串

C语言中字符串被编码为一个以 null 字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是 ASCII 字符码。

布尔代数

位向量是固定长度为 $\omega$ 由 0 和 1 组成的串，位向量的运算可以定义成参数的每个对应元素之间的运算。

位向量一个很有用的应用就是表示有限集合: 我们可以用位向量 $[a_{\omega-1}, a_{\omega-2}, \cdots, a_0]$ 编码任何子集 $A\in 0, 1, \cdots, \omega-1$ ，其中 $a_i=1$ 当且仅当 $i\in A$ 。

• 对于任意整数 $\omega>0$ ，长度为 $\omega$ 的位向量上的布尔运算 |、&、~ 形成了一个布尔代数。
• 对于任意整数 $\omega>0$ ，长度为 $\omega$ 的位向量上的布尔运算 ^、&、~ 形成了一个布尔环。

整数表示

无符号数的编码

假设有一个整数数据类型有 $w$ 位，定义向量 $\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ 。那么 $B2U_w$(Binary to Unsigned) 为:

$$B2U_w(\vec{x}) := \sum_{i=0}^{w-1}x_i2^i$$

表示的最大整数值为 $\sum_{i=0}^{w-1}2^i=2^w-1$ 。无符号数和二进制编码一一对应，函数 $B2U_w$ 是一个双射。

补码编码(two’s-complement)

补码是表示有符号数最常见的方式: 将字的最高有效位解释为负权，用函数 $B2T_w$(Binary to Two’s-complement) 来表示。定义向量 $\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ 。那么 $B2T_w$ 为:

$$B2T_w(\vec{x}):=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$$

补码能表示的范围为: $[-2^{w-1}, 2^{w-1}-1]$ ，补码同样构成一一对应，函数 $B2T_w$ 也是一个双射。

反码(Ones’Complement)和原码(Sign-Magnitude)

除了补码之外，还有反码和原码可以用来表示有符号数。

• 反码: 除了最高有效位的权是 $-(2^{w-1}-1)$ 而不是 $-2^{w-1}$，它和补码是一样的 $$B2O_w(\vec{x}) := -x_{w-1}(2^{w-1}-1)+\sum_{i=0}^{w-2}x_i2^i$$
• 原码: 最高有效位是符号位，用来确定剩下的位应该取负权还是正权 $$B2S_w(\vec{x}) := (-1)^{x_{w-1}}\times \sum_{i=0}^{w-2}x_i2^i$$

  反码和原码对于 0 都有两种表示方式，对于 +0 两者都表示为 $[00\cdots 0]$ ，而 -0 在原码中表示为 $[10\cdots 0]$ 在反码中表示为 $[11\cdots 1]$

有符号数和无符号数之间的转换

考虑下面这段代码

short int v = -12345;
unsigned short uv = (unsigned short) v;
printf("v = %d, uv = %u\n", v, uv);

输出: v = -12345, uv = 53191 ，其含义是强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。

C语言中执行一个运算时，它的一个运算数是有符号的而另一个是无符号的，那么C语言会隐式地将有符号参数强制类型转换为无符号数来执行运算。例如 -1 < 0u 会返回 false，因为左边的操作数将被隐式地转换为无符号数: $-1\to -1+2^{w}$

扩展一个数的位表示

即从一个较小的数据类型转换到一个较大的类型同时又保持数值不变。

• 要将一个无符号数转换为一个更大的数据类型，只要简单的在表示的开头加0，这种运算被称为零扩展(zero extension);
• 要将一个补码转换为更大的数据类型，可以执行一个符号扩展(sign extension)，在表示中添加最高有效位的值:
  • 将原始位 $\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ 扩展为 $\vec{x}’=[x_{w-1},x_{w-1},\cdots, x_{w-1}, x_{w-2}, \cdots, x_0]$

即 $B2T_{w}(\vec{x}) = B2T_{w’}(\vec{x}’)$ 。要证明这个，其实只需证明扩展1位时成立即可，即要证明

$$B2T_{w+1}([x_{w-1},x_{w-1},x_{w-2},\cdots,x_0])=B2T_{w}([x_{w-1},x_{w-2},\cdots,x_0])$$

由于

$$\begin{align*} B2T_{w+1}([x_{w-1},x_{w-1},x_{w-2},\cdots,x_0])&=-x_{w-1}2^w+\sum_{i=0}^{w-1}x_i2^i\\ &=-x_{w-1}2^w+x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i\\ &=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i\\ &=B2T_{w}([x_{w-1},x_{w-2},\cdots,x_0]) \end{align*}$$

这就证得了上结论。

观察下面的代码:

short sx = -12345;
unsigned uy = sx;
printf("uy = %u\n", uy);

在一台大端法机器中输出 uy = 4294954951 ，这表明当把 short 转换成 unsigned 时会先改变大小，再完成从有符号到无符号的转换，也就是说 (unsigned) sx 等价于 (unsigned) (int) sx

截断数字

即不用额外的位来扩展一个数值，而是减少表示一个数字的位数。截断一个数字可能会改变它的值，溢出的一种形式。

• 截断无符号数: 令 $\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ ，而 $\vec{x}’ = [x_{k-1},x_{k-2},\cdots,x_0]$ 为将 $\vec{x}$ 截断为 $k$ 位的结果，令 $x=B2U_w(\vec{x})$ ，$x’=B2U_k(\vec{x}’)$ ，则 $x’ = x\bmod{2^k}$ 。(直接带入即可证明)
• 截断补码数值: 令 $x=B2U_w(\vec{x})$，$x’=B2T_k(\vec{x}’)$ ，则 $x’=U2T_k(x\bmod{2^k})$

整数运算

无符号加法

考虑两个非负整数 $x$ 和 $y$ 满足 $0\le x, y< 2^w$ ，表示它们的和可能需要 $w+1$ 位，这样就会造成字节膨胀。

定义运算 $+^u_w$ ，该运算把整数和 $x+y$ 截断为 $w$ 位得到的结果，再把这个结果看作一个无符号数，即取 $(x+y)\bmod{2^w}$ 。

检测无符号数加法中的溢出: 对在范围 $0\le x$ ，$y\le UMax_w$ 中的 $x$ 和 $y$ ，令 $s = x +_{w}^{u} y$ , 则对计算 $s$ ，当且仅当 $s<x$ 或者等价地 $s<y$ 时发生了溢出。

$Proof.$ 首先需要注意到 $x+y\ge s$ ，如果 $s$ 没有发生溢出，则 $s\ge x$ 。另一方面，如果 $s$ 发生了溢出，则有 $s = x+y-2^w=x+(y-2^w)< x$

补码加法

对整数 $x$ 和 $y$ 满足 $-2^{w-1}\le x, y\le w^{w-1}-1$ ，定义 $x+_w^t y$ 为整数和 $x+y$ 被截断为 $w$ 位的结果，并将这个结果看作补码数。有:

$$x+_w^t y = \begin{cases} x+y-2^w, &2^{w-1}\le x+y\\ x+y, &-2^{w-1}\le x+y< 2^{w-1}\\ x+y+2^w, &x+y<-2^{w-1} \end{cases}$$

检测补码加法溢出: 对在范围 $TMin_w\le x$ ，$y\le TMax_w$ 中的 $x$ 和 $y$ ，令 $s = x +_{w}^{t} y$ , 则对计算 $s$ :

• 当且仅当 $x>0$ ，$y>0$ 但 $s\le 0$ 时发生了正溢出;
• 当且仅当 $x<0$ ，$y<0$ 但 $s\ge 0$ 时发生了负溢出.

补码的非

对满足 $TMin_w\le x\le TMax_w$ 中的 $x$ ，其补码的非 $-^t_w x$ 由下式给出

$$-^t_w x = \begin{cases} TMin_w , &x=TMin_w\\ -x, &x> TMin_w \end{cases}$$

也就是说，对 $w$ 位的补码加法来说，$TMin_w$ 是自己的加法的逆，而其他任何数值的 $x$ 都有 $-x$ 作为其加法的逆。

求补码非的简便方法:

1. 对每一位求补(取反)，再对结果+1，也就是 -x 和 ~x+1 等价。
2. 假设 $k$ 是最右边 1 的位置，即将 $x$ 的位级表示为: $[x_{w-1},\cdots, x_{k+1},1,0,\cdots, 0]$ ，然后对 $k$ 左边的所有位取反(01110 $\to$ 10010)

补码乘法

对整数 $x$ 和 $y$ 满足 $-2^{w-1}\le x, y\le w^{w-1}-1$ ，定义 $x^t_w y$ 为整数和 $xy$ 被截断为 $w$ 位的结果，并将这个结果看作补码数。将一个补码数截断为 $w$ 位相当于先计算该值模上 $2^w$ 再将无符号数转换为补码，即

$$x*^t_w y = U2T_w((x\times y)\bmod{2^w})$$

无符号和补码乘法的位级等价。

乘以常数

对于大多数机器来说整数乘法指令都相当慢，而加法、减法、位级运算和移位等运算很快，因此编译器使用了用移位和加法运算的组合来对乘法指令进行优化。

首先考虑乘以 2 的幂次，$x\times 2^k$ 只需要将 $x$ 的位级表示左边加 $k$ 个 0 即可。如果是固定字长，则其高 $k$ 位被舍弃，可以发现左移一个数值等价于执行一个与 2 的幂相乘的无符号乘法。而乘一个常数 $C$ 只需要将 $C$ 改写为 2 的幂次的和或者差，例如执行 $x*14$ 编译器会将乘法重写为 $(x<<3)+(x<<2)+(x<<1)$ 或者更优地改为 $(x<<4)-(x<<1)$

除以2的幂

整数除法总是舍入到 0，即对于 $x\ge 0, y>0$ ，结果是 $\lfloor\frac{x}{y}\rfloor$ ，而对于 $x\le 0, y>0$ ，结果是 $\lceil \frac{x}{y}\rceil$ 。无符号数的右移一定是逻辑右移。

除以 2 的幂的无符号除法原理: C 变量 $x$ 和 $k$ 有无符号数值 $x$ 和 $k$ ，且 $0\le k> k` 产生数值 $\lfloor \frac{x}{2^k}\rfloor$

除以 2 的幂的补码除法向下舍入原理: C 变量 $x$ 和 $k$ 有补码值 $x$ 和无符号数值 $k$ ，且 $0\le k> k` 产生数值 $\lfloor \frac{x}{2^k}\rfloor$

浮点数

二进制小数

考虑一个形如 $b_mb_{m-1}\cdots b_1b_0b_{-1}b_{-2}\cdots b_{-n}$ 的表示法，其中每个二进制数字，或者称为位，$b_i$ 的取值为 0 或 1 ，这种表示方法定义如下:

$$b = \sum_{i=-n}^{m} 2^i\times b_i$$

二进制小数点向左移动一位相当于这个数除以 2 ，向右移动一位相当于这个数被乘以 2。但是定点表示法不能很有效地表示非常大的数字。

1. 将二进制小数转换为十进制小数: $110.101_2 = 2^2 + 2^1 + 2^{-1} + 2^{-3} = 6.625$
2. 将十进制小数转换为二进制小数: 整数部分：除 2 取余数，直到商为 0 ，小数部分：乘 2 取整数，直到小数部分为 0 。比如表示 0.1 : $$\begin{align*} 0.1 \times 2 = 0.2 \tag0\\ 0.2\times 2 = 0.4 \tag0\\ 0.4\times 2 = 0.8 \tag0\\ 0.8\times 2 = 1.6 \tag1\\ 0.6\times 2 = 1.2 \tag1\\ 0.2\times 2 = 0.4 \tag0\\ \cdots \end{align*}$$

如此就可以将 0.1 表示为 $0.000110…$ ，如此循环，所以需要四舍五入存储到计算机当中，这就造成了误差。除此之外还比如 $0.875=0.111_2$ 。

IEEE浮点表示

IEEE浮点标准用 $V = (-1)^s\times M\times 2^E$ 的形式来表示一个数:

• 符号(sign) $s$ : 决定 $V$ 是整数( $s=0$ ) 还是负数( $s=1$ ) ，而对于数值 0 的符号位解释作为特殊情况处理;
• 尾数(significand) $M$ : $M$ 是一个二进制小数，范围是 $1\sim 2-\varepsilon$ 或者 $0\sim 1-\varepsilon$ ;
• 阶码(exponent) $E$ : 作用是对浮点数加权，这个权重是 2 的 $E$ 次幂(可能是负数)。将浮点数的位表示划分为 三 个字段，分别对这些值进行编码:
  • 一个单独的符号位 $s$ 直接编码符号 $s$ ;
  • $\rm{exp}$: 阶码位，以移码形式存储，位数决定数据的范围，用 $\rm{e}$ 表示，其阶码值为 $\rm{E}$ 。$\rm{k}$ 位的阶码字段 $\rm exp =$ $e_{k-1}\cdots e_{1}e_0$ 编码阶码值 $\rm E$ ;
  • $\rm frac$ : 尾数位，以原码形式存储，小数部分，其尾数决定小数的精度。$n$ 位小数字段 $\rm frac= $ $f_{n-1}\cdots f_1f_0$ 编码尾数 $M$ ，但是编码出来的值也依赖于阶码字段的值是否等于0。

在单精度浮点格式(C语言中的 float ) 中，$\rm s$、$\rm exp$ 和 $\rm frac$ 的字段分别为 1 位，$k=8$ 位和 $n = 23$ 位，得到一个 32 位的表示。
在双精度浮点格式(C语言中的 double ) 中，$\rm s$、$\rm exp$ 和 $\rm frac$ 的字段分别为 1 位，$k=11$ 位和 $n = 52$ 位，得到一个 64 位的表示。

以一个 32 位的 float 为例，由符号位、指数位和小数位组成，如图所示

• 符号位: 1 位，0 表示正数，1 表示负数;
• 指数位: 8/11(float/double) 位表示指数，可以表示 256/2048 种状态;

  因为指数可正可负，在 IEEE 标准里并没有选择用补码来表示负数，而是选择了直接向左平移(又叫阶码)，8 位的范围是 $[0, 255]$ ，我们将它向左平移一半(取127)，范围就变成了 $[-127, 128]$ ，也就是说指数位减去127才是真实的指数，比如 12(00001100) 代表 12-127 = -115 。这里减去的数叫偏移量(biase)，对单精度来说是127，对双精度来说是1023。

• 小数位: 23/52位，表示底数。显然底数的长度决定了类型的精度，决定了到底能存几位有效数字，而指数位只是表示小数点的位置;

Q. 将 $78.625$ 转化为单浮点数形式。

A. 首先将 $78.625$ 转化为二进制表示，为 $1001110.101$ ，即 $1.001110101\times 2^6$ 。
考虑指数位为 $6+127=133=10000101_2$ ，并将底数的小数点后面添加0补到23位，得到结果为:

$$\color{red}{0}\color{green}{10000101}\color{blue}{00111010100000000000000}$$

IEEE-754浮点转换器: https://www.h-schmidt.net/FloatConverter/IEEE754.html

注意到，由于第一位总是1，所以就不需要显式地表示它，这就获得了一个额外的精度位。

非规约数 & 正零和负零

考虑到指数范围为 $[-127, 128]$ ，也就是说能表示最大精度(0x00000000)为 $\pm2^{-127}$ 。

为了表示更小的数，在指数位全为0时，丢弃掉最高位为1的束缚，将最高位规定为0,将”全0指数位”规定为-126而不是本来的-127，用于表示绝对值小于 $2^{-126}$ 的数，这样的数就可以叫做非规约数(denormal number)

比如 $\color{red}{0}\color{green}{00000000}\color{blue}{00111010100000000000000}$ 表示的数为 $0.001110101\times 2^{-126}=1.110101\times 2^{-129}$ ，这样就可以表示 $\pm 2^{-126-23} = \pm2^{-149}$ 。

而对于 0 的表示，因为符号位可以取1和0,即对应于负零和整零，在高级应用层面对于正零和负零的判定各不相同，C++中负零和整零相等，并且布尔值都对应于 false ，在运算过程一个理论答案为零的结果既可能被计算为正零，也可能被计算为负零。

逐渐溢出

规格数的最小值为 $0(00000001)0\cdots 0_2 = 2^{-126}$
非规格数的最大值为 $0(00000000)1\cdots 1_2 = (1-2^{-23})2^{-126}$ ，基本可以看做 $2^{-126}$ 的开区间，从非规格数过渡到规格数时，相当于指数 $-126$ 不变，底数进位到隐藏的高位。从而实现了平稳的值域过渡，刚好覆盖了实数轴，这种特性叫做逐渐溢出(gradual overflow)

而这也是前面非规约数使阶码值为 $1-\rm Bias$ 而不是 $-\rm Bias$ 的原因。

当二进制码从 0x00000000 不断递增时，它表示的浮点数值也是逐渐递增的。这对于非规约数到规约数来说表现为”逐渐溢出”，而对于规约数来说，小数部分不全为1的时候显然; 而当小数部分全为1的时候，再下一个数是小数位清零，指数位加1。
例如 $0(0..01)11..11$ 对应浮点数的下一个是 $0(0..10)00..00$ ，而 $0(0..01)11..11$ 对应整数的下一个也是 $0(0..10)00..00$ 。根据这个特性，可以像整数一样对浮点数进行基数排序。

无穷(inf)

用指数位全为1的状态表示无穷，根据符号位的不同有正无穷和负无穷之分。无穷支持一些数学意义上的运算:

• 同号无穷被认为相等，正无穷 > 所有规约数 > 负无穷
• 无穷与规约数进行四则运算仍是无穷

C++ 中可以使用 1/0.0 或者 1e1000 等赋值来得到一个无穷，他们都是一样的无穷，本质上是表示”超过存储范围”。输出 inf 或者 -inf 。

非数值(NaN)

非数值与无穷一样使用全为1的指数位表示，为了区分开来，小数位全为0时表示无穷，其他所有情况表示非数值情况。

浮点数的范围和精度

对于32位规约数来说，指数位包括 $[-127, 128]$ ，但是由于左右端点表示其他值，所以实际指数位为 $[-126,127]$ 。

范围: 考虑正数，前面计算过最小的规约数为 $2^{-126}$ ，而最大的规约数为 $0(11111110)1…1_2 \approx 2^{128}$ ，所以极限范围就是 $[2^{-126}, 2^{128})$ ，转换为十进制就大约是 $[1.175\times 10^{-38}, 3.403\times 10^{38}]$ 。如果算上非规约数，那下界可以达到 $2^{-149}\approx 1.401\times 10^{-45}$ 。

精度: 精度即底数有效数字的位数，底数有23位，而换算成十进制下就大约是7位小数，双精度的话就是大约15位。

舍入

因为表示方法限制了浮点数的范围和精度，所以浮点运算只能近似地表示实数运算，因此，对于值 $x$，我们使用一种系统的方法，能够找到最接近的匹配值 $x’$，它可以用期望的浮点形式表示出来，这就是舍入运算的任务。

IEEE浮点格式定义了四种不同的舍入方式，默认的方法是找到最接近的匹配，而其他三种可用于计算上界和下界。

• 向偶数舍入: 它将数字向上或者向下舍入，使得结果的最低的有效数字是偶数。
• 向零舍入：把正数向下舍入，把负数向上舍入。
• 向下舍入：把正数和负数都向下舍入。
• 向上舍入：把正数和负数都向上舍入。