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

作者: 程序员七哥 | 来源:发表于2019-09-21 10:46 被阅读0次

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

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

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

1. 信息存储

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

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

1.1 寻址和字节顺序

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

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

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

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

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是一个小端法机器。下面在放一张在各个机器测试的不同结果，更加全面的对比图：

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，能够设计一种代数，用来研究逻辑推理的基本原则。

布尔运算：

3.png

1.4 C语言中的位级运算

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

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

4.png

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

1.5 C语言中的移位运算

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. 整数表示

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

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]$
用一个函数来表示：
$B 2 U_{w}(\vec{x}) \doteq \sum_{i=0}^{w-1} x_{i} 2^{i}$
计算规则：
$\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.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}$

最高有效位即 $x_{w-1}$ 也称为符号位。符号位等于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}$

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

最大值为： $T M a x_{w} \doteq \sum_{i=0}^{w-2} 2^{i}=2^{w-1}-1$

例如以长度为4为例， $T M i n_{4}=B 2 T_{4}([1000])=-2^{3}=-8$ , 而 $T M a x_{4}=B 2 T_{4}([0111])=2^{2}+2^{1}+2^{0}=4+2+1=7$

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

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

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

对满足 $T M i n_{w} \leqslant x \leqslant T M a x_{w}$ 的 x 有：
$T 2 U_{w}(x)=\left\{\begin{array}{ll}{x+2^{w},} & {x<0} \\ {x,} & {x \geqslant 0}\end{array}\right.$

比如， $T 2 U_{16}(-12345)=-12345+2^{16}=53191$ ,同时 $T 2 U_{w}(-1)=-1+2^{w}=U M a x_{w}$ 。

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

对满足 $0 \leqslant u \leqslant U M a x_{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.$

3. 整数运算

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

3.1 无符号加法

原理：无符号加法，对满足 $0 \leqslant x, \quad y<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.$

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

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

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

原理：无符号数求反

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

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

3.2 补码加法

原理：补码加法

对满足 $0 \leqslant x, \quad y \leqslant U M a x_{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.$

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

对满足 $T M i n_{w} \leqslant x, \quad y \leqslant T M a x_{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}$ ,编译器会将乘法重写为 $(x<<3)+(x<2)+(x<<1)$ ,将乘法替换为三个移位和一个加法。

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

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

4. 浮点数

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

4.1 二进制小数

十进制数转换描述定义：
$d=\sum_{i=-n}^{m} 10^{i} \times d_{i}$

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

二进制数转换描述定义：
$b=\sum_{i=-n}^{m} 2^{i} \times b_{i}$

例如， $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} $

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

8.png

4.2 IEEE浮点表示

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

符号（sign）s决定这数是负数（s=1）还是正数（s=0）。
尾数（signnificand） M是一个二进制小数，它的范围是 $1 \sim 2-\varepsilon$ 。
阶码（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位的表示。

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编码。在位级上理解这些编码有助于写出全部数值范围上正确运算的程序。
由于编码长度有限，计算机运算会产生溢出。
使用浮点运算要小心，因为只有有限的范围和精度。

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