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

2019-09-21 本文已影响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.$