CS:APP读书笔记-2-信息的表示与处理

第二章：信息的表示与处理

我们的操作系统能力那么大，它又是怎么来表示这些东西呢？每天打开电脑，我们要面对的文本，英文字母，数字，符号，中文和各种风马牛不相及的语言，他们各自的字符加起来成千上万，这些看起来完全不同的东西，如何在计算机内部进行统一的表达？在第一章，我们提到了ASCII这一种编码方式，但是它能表示的仅仅是很小一部分。整数，分数，实数我们又该怎么表示？在这一章，我们会主要学习三种数字的表达方式：无符号数、有符号数、浮点数。

在这里，我觉得有必要提及一下，我们常说的64位操作系统，这里面的64是什么意思。在第一章，我提到了CPU这一概念，CPU能够一次性处理的最长数据长度我们一般称为多少位的操作系统，而这个长度，通常也是寄存器的大小。如果有兴趣，可以去搜索寄存器是什么。

同时，在这一章，也会适当的引入溢出(overflow)这一概念来更好的了解为什么数据的表示不是无限的。

信息存储

第一章我们提到，计算机内部8bit为1byte。而byte就是计算机内存寻址的最小单位，它无法单独的操作某一个bit位。在程序运行起来后，我们的操作系统会把这个运行的程序和它所需的环境、数据统一抽象成一个概念：进程。在进程里，它能够寻址的空间是一个巨大的连续数组，通常来说，如果是64位操作系统，这个空间一般是0x00000000~0xffffffff。这个空间我们一般称为虚拟内存(virtual memory)。内存里面的每一个字节，都有一个唯一的数字来标识，这个数字一般称为地址(address)。由于抽象的存在，这一片地址空间看起来是连续的，但是实际上它的映射一般都是零散的。

在上面出现了一种表示方法：0xffffffff，这是一种十六进制表达。我们以10进制下的16作为例子，同一个数的不同进制表示如下：

\[16(10) = 10(16) = 20(8) = 10000(2)\]

一般来说，十六进制数据前面我们会加上0x，八进制数据前加上0，二进制数据前加上0b。

由此可见，32位的操作系统，它的寻址空间就是 0~2^32 - 1。而这刚好就是4GB(4*2^30)。现在的64位操作系统，寻址空间巨大，大概16EB。但是一般不会用这么长。现在来看，一般使用了48bit空间寻址。

以第一章的hello.c为例，我们可以把它编译成32位或者64位，只需要带上编译参数即可，例如：

gcc -m32 hello.c
gcc -m64 hello.c

但是这一命令，很可能运行失败，因为你的系统大概率没有安装32位应用程序所需要的库。如何安装libc-i386，还请自行查阅。如无特殊说明，后续都将会是64位系统下进行操作。

数据的长度

常见的一些表示数据长度的声明如下。针对前4项，还可以使用unsigned前缀，来将声明变成一个无符号数。除了下面这些常见声明，你还可以使用更确定的声明方式，不过这需要你引入头文件stdint.h，比如uint16_t。这种声明会确保你得到一个无符号的16比特数据表示。为什么我们平时使用一些约定俗成的short，int这种也无伤大雅？其实很多时候这种未精确定义的类型，它们的长度依赖于平台和编译器的实现，如果你想要准确的长度，那么使用int32_t这种明确标定的类型是很好的选择。

声明	长度
char	1
short	2
int	4
long	8
int32_t	4
int64_t	8
char *	8
float	4
double	8

有无符号对我们来说重要吗？很重要，因为这确保了他们的表示范围以及最后转化机器指令的时候不会出错。假如在使用int32_t的时候，却和uint32_t相比，无疑会出现纰漏。有一个很有趣的小实验，假如有以下两个数组，我们定义为：char a[2] = {0xfb, 0xf4}；unsigned char b[2] = {0xfb, 0xf4}；在使用printf打印他们的十六进制表示，会出现不同。

寻址和字节顺序

在我们确定了类型的长度后，随之而来的一个问题就是顺序。这其实也是一个制造商们的习惯问题，比如我们有如下数据int32_t data=0x12345678，假定data是存放在地址0x100处，那我们该怎么排布这些数据呢？有两种方式供我们选择：

为什么一个地址能表示两个十六进制数？因为一个地址是8bit，但是十六进制最大的数是F(16)=1111(2)。

	0x100	0x101	0x102	0x103
data（大端）	0x12	0x34	0x56	0x78
data（小端）	0x78	0x56	0x34	0x12

这就是计算机内两种表示法：大端（最高有效位在前面）、小端（最低有效位在前面）。

在网络上，我们的数据传输一般采用大端，而在目前的Intel上，一般采用小端。这就是我们在网络编程时，会用到的一个函数族hton(l/s) ntoh(l/s)的由来，如果不统一我们的数据排列形式，那么势必会引起误会。如果你想确定自己电脑的大小端，想一想该怎么编写C代码。

提示：强制类型转换来分别打印一个int的每一个字节数据。

字符串的表示

在C里面，字符串是一个以\x00结尾的字符数组。注意，这表示在不同语言内，它们拥有自己的字符串表示方法。例如在Go语言内，字符串不再是以\x00结束，相反它取消了\x00，把所有的字符串糅合在一起，通过一个结构来表示，这个结构可以表达成如下形式。这也导致了在进行Go逆向时最讨厌的问题之一，你不能很快的通过字符串进行定位了。

struct string{
    str_addr;
    str_size;
}

在使用ASCII码表时，我们只需要依次的将每个字节映射到ASCII表上即可。例如字符串”12345“，在内存中它就是0x31 0x32 0x33 0x34 0x35 0x00。这里我们说的时ASCII表，除此之外，我们还有常见的UTF8，你也可以试试中文的”你好“，通过强制转换来观察每一个字节是什么。

代码的表示

代码意味着一串可以被CPU理解并执行的字节序列。这里就有一个概念出现了—ABI(Application Binary Interface)¹。也许你听说过API。各个系统的ABI一般来说都是不兼容的，这也意味着你在Windows上的应用程序是没法直接在Linux上运行的，你在MAC上的安装包dmg，在Windows和Linux上也难以使用。之前我看到有坛友问，Linux上的unistd.h能在Windows上使用吗，很遗憾这是不可能的。

一些简单的操作

布尔运算：&(与)、

(或)、~(非)、^(异或)

逻辑操作：&&(同时满足)、

(满足一个)、!(取反)

以上操作具体含义自行搜索，都很简单。

整数的表示

我们常说的整数，一般指有符号整数和无符号整数。接下来就分别说明下两者是如何编码的。

无符号整数

这个是最简单的一种形式，直接按照进制转化即可。注意，这种表示方法只能表示0~2^w-1的数据。w就是我们常说的位数，在32位系统上，w就是32。

有符号整数

在这里，有些大聪明肯定想。既然要区分符号，那么最高位用来做符号位不就好了吗？这样的话，对于一个4bit的数据，1001₂ = -1，同时0001₂ = 1。完美！注意到一个问题了吗，那0该怎么办呢？它就会对应两种表达方式1000₂ 0000₂。这就是一种最直观的编码形式—原码。下面，我们将采用8bit数据，进行不同编码下的表示，即反码、补码。

反码：最高位表示符号，剩下的位数表示数值。如果是负数，则对数值位取反。

补码：和反码一致，但是最后多一步：+1。

在计算机系统内，我们用补码来表示有符号整数。为什么要采用补码呢，请考虑在使用原码时计算如下等式：

1 - 1 = 1 + （-1） = 0000 0001₂ + 1000 0001₂ = 1000 0010₂ = -2

如果采用反码形式，我们就能规避这一错误，但是请注意，我们这里得到了一个很奇怪的表达，\(\pm0\)，也就是说0同时拥有了两种表达方式。

1 - 1 = 1 + （-1） = 0000 0001₂ + 1111 1110₂ = 1111 1111₂ = 0

在此基础上，如果我们使用补码呢？同时，我们可以多一个数字来进行表示了，那就是-128

1 - 1 = 1 + （-1） = 0000 0001₂ + 1111 1111₂ = 0000 0000₂ = 0

-1 + （-127）= 1111 1111₂ + 1000 0001₂ = 1000 0000₂ = -128

在以上的计算中，我们将减法变成了对负数的加法。同时很好的定义了0，也扩大了编码能表示的数据。现在使用补码，我们能够表示的范围是[-128,127]。

注意到了吗，符号位同时参与到了运算。这种情况下，我们设计电路很容易，但是原码就会导致出错。而反码会导致0的重复定义，但是补码能够正确的表达，同时不重复定义0，还让我们能够多一个能表达的最小值。

溢出的问题

在上文的计算中，也许你已经发现一个问题，这个等式中，假如使用的是8bit数据，最后不是会变成1 0000 0000₂吗，多出来的1去哪里了？

1 - 1 = 1 + （-1） = 0000 0001₂ + 1111 1111₂ = 0000 0000₂ = 0

上面的计算是基于有符号整数表示，假如我们把它看成无符号整数呢？注意，最高位不再代表符号了。

1 + 255 = 0000 0001₂ + 1111 1111₂ = 0000 0000₂ = 0

这一个奇怪的现象被称为溢出。关键原因就是，计算机内部，对整数表示是有限的。我们采用了8bit数据，所以我们无法表示超过255的无符号整数。

由于减法可以被转化成负数的加法，所以溢出的问题要特别注意。

除此之外，尤其要注意的另一种情况，转换。考虑以下代码：

int str_longer(char *s1, char *s2){
    return strlen(s1) - strlen(s2) > 0;
}

提示，查看strlen的定义和typedef。

溢出的问题直到现在，都是我们不得不面对的问题。有兴趣的朋友，可以自行去搜索这个CVE和它的分析报告。

CVE-2022-42475

浮点数

现在终于到了我们最头疼的东西，浮点数。这就是我们经常会碰到一些计算机奇怪计算的小数的源头，它目前采用IEEE的标准，我们会简单介绍它到底是怎么计算和编码的。 首先我们要了解，我们日常使用的小数，采用十进制表示。那么对于一个形如111.111₂的二进制小数，我们该怎么来理解它？

对于十进制，小数点.的往右移动等价*10，左移等价/10。同理，对二进制小数而言，右移等价*2，左移等价/2。所以对于111.111₂，我们可以很快的得到这是111.111₂ = 7\(\frac{7}{8}\)。所以对于\(\frac{1}{5}\)这种分数，十进制小数0.2可以精确的表示，但是二进制小数只能近似。我们这里有一张近似表以供查看。

表示	十进制
\(0.0_2\)	\(0.0_{10}\)
\(0.01_2\)	\(0.25_{10}\)
\(0.0011_2\)	\(0.1875_{10}\)
\(0.0011010_2\)	\(0.203125_{10}\)

浮点表示对\(V = x \times 2^y\)这样的有理数进行编码。0.111…111₂这样表示刚好小于1的数，我们采用\(1-\epsilon\)进行表示。根据IEEE的标准，采用\(V=(-1)^s \times M \times 2^E\)的形式来表示一个数，它们的符号含义如下：

1. s：符号sign，表示正负。
2. M：有效数据significand(原文中这里用的significand，我查了查IEEE标准，这里是fraction)。存储一个二进制小数，它的范围通常是\(1 \sim 2-\epsilon\)或者\(0\sim 1-\epsilon\)​
3. E：阶码exponent。对M进行加权，权重为\(2^E\)。

对这三个字段进行编码，规则如下：

1. 符号位直接编码s。
2. E为k位的阶码字段，编码为\(exp=e_{k-1}e_{k-2}...e_2e_1e_0\)。
3. M为n位的小数字段，编码为\(frac=f_{n-1}f_{n-2}...f_2f_1f_0\)。

三者顺序排布，在常见的单精度(32位)下，s=1、k=8、n=23。双精度(64位)时，s=1、k=11、n=52。下面介绍三种情况来如何编码。

规格化

英文原文是Normalized,直译过来叫归一。搞机器学习或者深度学习的同学看文档没少看这个词，经常数据要归一化，平整到0-1。这里代表最普遍的情况：exp不全为0或者1。这时候，exp字段被解释成偏置(biased)形式的有符号整数。（老演员了，和上面一样。）这时候有\(E=e-Bias\)。此时\(e=e_{k-1}e_{k-2}...e_2e_1e_0\)(无符号数e的位表示)，\(Bias=2^{k-1}-1\)。

小数字段frac被解释为\(0\le f < 1\)，且被表示为\(0.f_{n-1}...f_1f_0\)。此时，\(M=f+1\)。我们就此得到了浮点数V的表示。

非规格化

exp位全部为0。此时\(E=1-Bias,M=f\)。书中提到了非规格化的两种好处，虽然没理解，还是列出来

1. 能够表示数值0。因为普通情况下\(M\ge 1\)。
2. 对于非常接近0的数，其可能的数值均匀分布地接近0。

特殊值

exp位全部为1。frac字段为全0时，表示无穷\(\infty\)。frac不为0，表示“NaN”(not a number)。

现在，假设我们s=1、k=4、n=3我们来尝试做一些表示

描述	位表示	e	E	f	M	\(V=2^E\times M\)	十进制（6位小数）
非规格化	0 0000 000	0	-6	\(\frac{0}{8}\)	\(\frac{0}{8}\)	\(\frac{0}{512}\)	0.0
…	0 0000 001	0	-6	\(\frac{1}{8}\)	\(\frac{1}{8}\)	\(\frac{1}{512}\)	0.001953
…	0 0000 111	0	-6	\(\frac{7}{8}\)	\(\frac{7}{8}\)	\(\frac{7}{512}\)	0.013672
规格化	0 0001 000	1	-6	\(\frac{0}{8}\)	\(\frac{8}{8}\)	\(\frac{8}{512}\)	0.015625
…	0 0001 001	1	-6	\(\frac{1}{8}\)	\(\frac{9}{8}\)	\(\frac{9}{512}\)	0.017578
…	0 1110 111	14	7	\(\frac{7}{8}\)	\(\frac{15}{8}\)	\(\frac{1920}{8}\)	240.0
无穷大	0 1111 000

由于非规格化使用了\(E=1-Bias,M=f\)，我们在最大地非规格化和最小地规格化之间平滑过渡。

舍入问题

由于表示方法的问题，所以我们会有一个无法绕开的问题，那就是表示的精度和范围。我们无法像在现实世界那样进行实数运算。在C里面，我们经常使用的是——向偶数舍入(向最接近的数进行舍入)²。也许你见过向上舍入或者向下舍入，但是这两种方式都会无法避免的引入一个统计问题，前者会导致偏大而后者偏小。采用向偶数舍入能够在平均值上避免这类问题。这里有个例子，我们可以参考下

方式	1.4	1.6	1.5	-1.5
向偶数舍入	1	2	2	-2

同样的，对于二进制小数我们有如下舍入方式，以保留2位为例。

1. 111.1011 = 111.11
2. 101.1110 = 110.00

由于精度和舍入的问题，所以浮点数运算时，我们要特别注意下我们熟知的加法结合律可能不再适用了。考虑如下代码

float a=1e10;
float b=3.14;
printf("%f\n", a+b-a);
printf("%f\n", a-a+b);

实际运算结果显示为0.000000和3.140000。浮点数自己的特性，导致在这种运算时结果往往出乎意料，而且由于精度问题，往往减法的值也不会如同我们预料中那样稳定。

有兴趣的可以尝试一下，在float的单精度下，我们如果做差，精度能够到达多少。看一下上面的非规格化最小值，尝试计算一次。

至此，我们完成了第二章的内容浏览。本书的第二章内容比较详实，如果深入探讨需要手动计算和理解才能深刻。有兴趣的朋友可以试试书后的练习题，加强了解。

参考链接

1. ABI的简单说明 https://zhuanlan.zhihu.com/p/386106883 ↩

2. 可以参考这个链接 https://blog.leodots.me/post/45-ieee754-rounding-rules.html ↩