CSAPP-2-信息的表示和处理

野性酷女 2023-08-17 15:34 134阅读 0赞

> 如果能完全理解计算机系统以及它对应用程序的影响，那么恭喜你，你走上了一条为数不多的大牛道路。

本文是深入理解计算机系统的第二篇文章，接着上一篇我们讲解的计算机系统开篇-[《计算机系统漫游》][Link 1]，本篇文章继续深入，一起来学习 **信息的表示和处理**。

本篇文章一共分为四部分，**信息存储**、**整数的表示**，**整数的运算** 和 **浮点数**。

## 1. 信息存储 ##

程序将内存视为一个非常大的字节数组，称为**虚拟内存**。内存中的每一个字节都由一个唯一的数字来标识，称为它的**地址**，地址的集合就称为**虚拟地址空间**。

> 每台计算都有一个字长，虚拟地址空间是以字来编码的，所以字长决定了虚拟地址空间的大小。对于一个字长为 w 位的机器而言，虚拟地址的范围为 0~![2^w][2_w] \-1 ,程序最多访问![2^w][2_w] 个字节。

### 1.1 寻址和字节顺序 ###

对于我们日常程序中的对象，它们在内存中往往是多字节的，那么我们必须知道两个规则：**这个对象的地址是什么？**以及**内存中如何排列这些字节？**

在几乎所有的机器上，字节都是被连续存储的，对象的地址为所使用字节中最小的地址。例如，一个int类型的变量x的地址为0x100，也就是地址表达式&x 的值为0x100，x的四个字节存储在内存0x100、0x101、0x102、0x103位置。

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

*  大端法：最高有效字节在最前面
 *  小端法：最低有效字节在最前面

![2438927-abb78ac47c334408.png][]

1.png

对于我们程序员来说，机器使用的字节顺序对我们是不可见的，无论哪种字节顺序的机器，我们的程序编译后得到的结果都是一样的，不过有时候字节顺序也会成为问题，这里不再详述什么情况下会产生问题，只作学习验证机器的字节顺序不同产生的不同结果。

# 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 *));
    }
    
    void test_show_bytes(int val) {
        int ival = val;
        float fval = (float) ival;
        int *pval = &ival;
        show_int(ival);
        show_float(fval);
        show_pointer(pval);
    }
    
    int main() {
        test_show_bytes(12345);
        return 1;
    }

运行上面的c语言程序，得到的结果如下：

39300000  
00e44046  
a8e7a4c2ff7f0000

参数12345的十六进制表示为0x00000393,结合上面的结果 39300000 说明我的linux64是一个小端法机器。下面在放一张在各个机器测试的不同结果，更加全面的对比图：

![2438927-d72246a3c0f727d9.png][]

2.png

上图指针 值完全不相同的原因是不同的操作系统使用不同的存储分配规则，不过需要注意的是Linux64使用的是8字节地址。

### 1.2 表示字符串 ###

C语言的字符串：一个以null(值为0)字符结尾的字符数组 如字符串"12345"编码为 61 62 63 64 65 使用ASCII编码。 linux系统可以使用 man ascii 命令查看ASCII编码表。

### 1.3 布尔代数简介 ###

二进制是计算机编码、存储和操作信息的核心。 将逻辑值 TRUE 和 FALSE 编码为1和0，能够设计一种代数，用来研究逻辑推理的基本原则。

布尔运算：

![2438927-6453d8d38d08edee.png][]

3.png

### 1.4 C语言中的位级运算 ###

> 事实上，我们平时代码中写的 | 就是OR(或)，& 就是AND(与)，~ 就是NOT（取反），^就是异或，本质上都是按位进行运算的。

以下是一些对char数据类型表达式求值的例子：

![2438927-13a5deb3dbc68b2e.png][]

4.png

正如示例说明的那样，确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制表示并执行二进制运算，然后再转换回十六进制。

### 1.5 C语言中的移位运算 ###

![2438927-2770680e38f02617.png][]

5.png

移位运算右移分为：逻辑右移和算术右移。

*  逻辑右移：在左端补0；
 *  算术右移：如果操作数的最高位是1则左端补1，如果为0则补0；

C语言中，几乎所有的编译器都对有符号数使用算术右移，无符号数使用逻辑右移。

Java中有明确定义，x>>k 表示算术右移k个位置，而x>>>k 会对x做逻辑右移。

这里说明一个移位运算有关的操作符优先级问题：

表达式 1<<2+3<<4 ，本意是（1<<2）+(3<<4),你可能也会犯这样的错误，其实前面的表达式等价于：1<<(2+3)<<4,因为**加法（减法）的优先级比移位运算要高**。

## 2. 整数表示 ##

下面的数据术语用来精确定义和描述计算机如何编码和操作整数。

![2438927-50ba500fef690230.png][]

6.png

### 2.1 无符号数的编码 ###

假设一个整数有w位，每个位的取值即0非1。

**原理：无符号数编码的定义**

对向量  
![\\vec\{x\}=\\left\[\\begin\{array\}\{cccc\}\{x\_\{w-1\},\} & \{x\_\{w-2\}\} & \{,\} & \{\\cdots, \\quad x\_\{0\}\}\\end\{array\}\\right\]][2_w]  
用一个函数来表示：  
![B 2 U\_\{w\}(\\vec\{x\}) \\doteq \\sum\_\{i=0\}^\{w-1\} x\_\{i\} 2^\{i\}][2_w]  
计算规则：  
![\\begin\{array\}\{l\}\{B 2 U\_\{4\}(\[0001\])=0 \\cdot 2^\{3\}+0 \\cdot 2^\{2\}+0 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=0+0+0+1=1\} \\\\ \{B 2 U\_\{4\}(\[0101\])=0 \\cdot 2^\{3\}+1 \\cdot 2^\{2\}+0 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=0+4+0+1=5\} \\\\ \{B 2 U\_\{4\}(\[1011\])=1 \\cdot 2^\{3\}+0 \\cdot 2^\{2\}+1 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=8+0+2+1=11\} \\\\ \{B 2 U\_\{4\}(\[1111\])=1 \\cdot 2^\{3\}+1 \\cdot 2^\{2\}+1 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=8+4+2+1=15\}\\end\{array\}][2_w]

### 2.2 补码编码 ###

上面介绍的是无符号编码的表示形式，但是我们应用中，还是希望表示负数值。最常见的有符号数计算机表示方式就是补码。

**原理：补码编码的定义**

对向量：  
![\\begin\{aligned\} \\vec\{x\}=\\left\[x\_\{w-1\}, x\_\{w-2\},\\right.&\\left.\\cdots, x\_\{0\}\\right\] \\\\ & B 2 T\_\{w\}(\\vec\{x\}) \\doteq-x\_\{u-1\} 2^\{w-1\}+\\sum\_\{i=0\}^\{w-2\} x\_\{i\} 2^\{i\} \\end\{aligned\}][2_w]

最高有效位即 ![x\_\{w-1\}][2_w] 也称为符号位。符号位等于1时，表示值为负，等于0时，值为非负，下面来看实际的计算示例：

![\\begin\{array\}\{l\}\{B 2 T\_\{4\}(\[0001\])=-0 \\cdot 2^\{3\}+0 \\cdot 2^\{2\}+0 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=0+0+0+1=1\} \\\\ \{B 2 T\_\{4\}(\[0101\])=-0 \\cdot 2^\{3\}+1 \\cdot 2^\{2\}+0 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=0+4+0+1=5\} \\\\ \{B 2 T\_\{4\}(\[1011\])=-1 \\cdot 2^\{3\}+0 \\cdot 2^\{2\}+1 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=-8+0+2+1=-5\} \\\\ \{B 2 T\_\{4\}(\[1111\])=-1 \\cdot 2^\{3\}+1 \\cdot 2^\{2\}+1 \\cdot 2^\{1\}+1 \\cdot 2^\{0\}=-8+4+2+1=-1\}\\end\{array\}][2_w]

这里让我们一起来考虑下补码所能表示的值的范围，最小值为：![T M i n\_\{w\} \\doteq-2^\{w-1\}][2_w].

最大值为：![T M a x\_\{w\} \\doteq \\sum\_\{i=0\}^\{w-2\} 2^\{i\}=2^\{w-1\}-1][2_w]

例如以长度为4为例，![T M i n\_\{4\}=B 2 T\_\{4\}(\[1000\])=-2^\{3\}=-8][2_w], 而 ![T M a x\_\{4\}=B 2 T\_\{4\}(\[0111\])=2^\{2\}+2^\{1\}+2^\{0\}=4+2+1=7][2_w]

补码编码也是取值范围内每个数字都有唯一的w位补码编码。

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

**原理：补码转换为无符号数**

对满足![T M i n\_\{w\} \\leqslant x \\leqslant T M a x\_\{w\}][2_w] 的 x 有：  
![T 2 U\_\{w\}(x)=\\left\\\{\\begin\{array\}\{ll\}\{x+2^\{w\},\} & \{x<0\} \\\\ \{x,\} & \{x \\geqslant 0\}\\end\{array\}\\right.][2_w]

比如，![T 2 U\_\{16\}(-12345)=-12345+2^\{16\}=53191][2_w] ,同时 ![T 2 U\_\{w\}(-1)=-1+2^\{w\}=U M a x\_\{w\}][2_w]。

**原理：无符号数转换为补码**

对满足 ![0 \\leqslant u \\leqslant U M a x\_\{w\}][2_w] 的 u 有：  
![U 2 T\_\{w\}(u)=\\left\\\{\\begin\{array\}\{ll\}\{u,\} & \{u \\leqslant T \\operatorname\{Max\}\_\{w\}\} \\\\ \{u-2^\{w\},\} & \{u>\\operatorname\{TMax\}\_\{w\}\}\\end\{array\}\\right.][2_w]

## 3. 整数运算 ##

在我们刚刚学习计算机时，大家有没有经历过，两个正数相加会得出一个负数，而比较表达式 x<y 和 x-y<0 会产生不同的结果呢？带着这些问题一起往下看吧。

### 3.1 无符号加法 ###

**原理：无符号加法，对满足** ![0 \\leqslant x, \\quad y<2^\{w\}][2_w] 的 x 和 y有：  
![x+\_\{w\}^\{u\} y=\\left\\\{\\begin\{array\}\{ll\}\{x+y,\} & \{x+y<2^\{w\}\} \\\\ \{x+y-2^\{w\},\} & \{2^\{w\} \\leqslant x+y<2^\{w+1\}\}\\end\{array\}\\right.][2_w]

比如：x=9，y=12 的位表示分别为\[1001\] 和 \[1100\]。它们的和是21，表示为5位的\[10101\]，产生溢出，丢弃最高位。

**原理： 检测无符号数加法中的溢出**

对在范围 ![0 \\leqslant x, \\quad y \\leqslant U M a x\_\{w\}][2_w],s=x+y，若s < x 或者等价的 s < y时，发生了溢出。

**原理： 无符号数求反**

对满足 ![0 \\leqslant x<2^\{w\}][2_w] ,的任意x，其w位的无符号逆元 ![\-\_\{w\}^\{u\} x][2_w] 表达式如下：

![\-\_\{w\}^\{u\} x=\\left\\\{\\begin\{array\}\{ll\}\{x,\} & \{x=0\} \\\\ \{2^\{w\}-x,\} & \{x>0\}\\end\{array\}\\right.][2_w]

### 3.2 补码加法 ###

**原理： 补码加法**

对满足![0 \\leqslant x, \\quad y \\leqslant U M a x\_\{w\}][2_w] 的整数x，y，有：

![x+\_\{w\}^\{t\} y=\\left\\\{\\begin\{array\}\{ll\}\{x+y-2^\{w\},\} & \{2^\{w-1\} \\leqslant x+y\} \\\\ \{x+y,\} & \{-2^\{w-1\} \\leqslant x+y<2^\{w-1\} \\quad \\begin\{array\}\{l\}\\\\ \\end\{array\}\} \\\\ \{x+y+2^\{w\},\} & \{x+y<-2^\{w-1\}\} \\end\{array\}\\right.][2_w]

**原理： 检测补码加法中的溢出**

对满足 ![T M i n\_\{w\} \\leqslant x, \\quad y \\leqslant T M a x\_\{w\}][2_w] 的x 和 y，令 s = x + y。当且仅当x>0,y>0，但s<=0时，计算s发生了正溢出。当且仅当 x<0,y<0，但s>=0时，计算发生了负溢出。

### 3.3 乘法和除法 ###

在大多数机器上，整数乘法指令相当慢，需要10个或者更多的时钟周期，然而**加法、减法、位运算、移位操作只需要一个时钟周期**。

因此，编译器使用了移位和加法运算的组合代替乘以常数因子的乘法。

**原理： 乘以2的幂**

例如：x\*14，利用14 = ![14=2^\{3\}+2^\{2\}+2^\{1\}][2_w] ,编译器会将乘法重写为 ![(x<<3)+(x<2)+(x<<1)][2_w] ,将乘法替换为三个移位和一个加法。

在大多数机器上，整数除法比乘法更慢，需要30个左右的时钟周期。

所以除法，也可以采用移位运算，相对于乘法这里采用的是右移，而不是左移。

## 4. 浮点数 ##

> 固定范围的数字，小数点前代表大小范围，小数点后代表精度，浮动小数点即平衡范围和精度，所以叫浮点数

### 4.1 二进制小数 ###

十进制数转换描述定义：  
![d=\\sum\_\{i=-n\}^\{m\} 10^\{i\} \\times d\_\{i\}][2_w]

例如：12.34 = ![1 \\times 10^\{1\}+2 \\times 10^\{0\}+3 \\times 10^\{-1\}+4 \\times 10^\{-2\}=12 \\frac\{34\}\{100\}][2_w]

二进制数转换描述定义：  
![b=\\sum\_\{i=-n\}^\{m\} 2^\{i\} \\times b\_\{i\}][2_w]

例如，![101.11\_\{2\}= 1 \\times 2^\{2\}+0 \\times 2^\{1\}+1 \\times 2^\{0\}+1 \\times 2^\{-1\}+1 \\times 2^\{-2\}=4+0+1+\\frac\{1\}\{2\}+\\frac\{1\}\{4\}=5 \\frac\{3\}\{4\} ][2_w]

增加二进制表示的长度可以提高表示的精度：

![2438927-a2df588a7f1a1ba5.png][]

8.png

### 4.2 IEEE浮点表示 ###

IEEE浮点标准用 ![V=(-1)^\{s\} \\times M \\times 2^\{E\}][2_w] 的形式来表示一个数：

*  符号（sign）s决定这数是负数（s=1）还是正数（s=0）。
 *  尾数（signnificand） M是一个二进制小数，它的范围是 ![1 \\sim 2-\\varepsilon][2_w]。
 *  阶码（exponent） E的作用是对浮点数加权，权重是2的E次幂。
 *  一个单独的符号位s
 *  k位的阶码字段 编码阶码E
 *  n位小数字段 编码尾数M

如下图：

在单精度格式（float），s，exp 和 frac 字段分别为 s=1，k=8, n = 23,得到一个32位的表示。

在双精度浮点格式（double）中，s=1、k=11、n=52位，得到一个64位的表示。

![2438927-8f7d2fdb1dbd9b15.png][]

9.png

### 4.3 C语言中的浮点数 ###

*  从int转换成float，数字不会溢出，但可能会被舍入；
 *  从int或float转成double，因为double范围更大，精度更高，所以能够精确的保留数值；
 *  从double转成float，因为范围要小，所以值可能溢出成正无穷或者负无穷，另外由于精度较小，可能舍入。
 *  从float或者double转成int，值将会向零舍入，例如1.999转换成1，-1.999转成-1。进一步来说，值可能会溢出。

## 5. 总结 ##

*  计算机将信息编码为位（比特），通常组成成字节序列。
 *  大多数机器对整数使用补码编码，而对浮点数使用IEEE标准754编码。在位级上理解这些编码有助于写出全部数值范围上正确运算的程序。
 *  由于编码长度有限，计算机运算会产生溢出。
 *  使用浮点运算要小心，因为只有有限的范围和精度。

> 本文涉及的数学知识较多，看着比较枯燥。如果是计算机专业的同学，应该会有些熟悉。 不过我们如果要做一名高级程序员，计算机底层是绕不过去的，所以还是撸起袖子，加油干吧！

## 推荐阅读 ##

*  [计算机系统漫游][Link 2]

[Link 1]: https://links.jianshu.com/go?to=http%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzA4MTE4NTg1OA%3D%3D%26mid%3D2247483654%26idx%3D1%26sn%3D25c528de5f245a65a27aa0b261382ca7%26chksm%3D9f999c2ba8ee153d79beb9db613c2f13594966c713ec889c1ade9463baf663b0e7fbb40e921a%26token%3D1690272020%26lang%3Dzh_CN%23rd
[2_w]: https://ss.csdn.net/p?https:
[2438927-abb78ac47c334408.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-abb78ac47c334408.png
[2438927-d72246a3c0f727d9.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-d72246a3c0f727d9.png
[2438927-6453d8d38d08edee.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-6453d8d38d08edee.png
[2438927-13a5deb3dbc68b2e.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-13a5deb3dbc68b2e.png
[2438927-2770680e38f02617.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-2770680e38f02617.png
[2438927-50ba500fef690230.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-50ba500fef690230.png
[2438927-a2df588a7f1a1ba5.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-a2df588a7f1a1ba5.png
[2438927-8f7d2fdb1dbd9b15.png]: https://ss.csdn.net/p?https://upload-images.jianshu.io/upload_images/2438927-8f7d2fdb1dbd9b15.png
[Link 2]: https://links.jianshu.com/go?to=http%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzA4MTE4NTg1OA%3D%3D%26mid%3D2247483654%26idx%3D1%26sn%3D25c528de5f245a65a27aa0b261382ca7%26chksm%3D9f999c2ba8ee153d79beb9db613c2f13594966c713ec889c1ade9463baf663b0e7fbb40e921a%26scene%3D21%23wechat_redirect