CSAPP之信息的表示和处理

前言

这章很有意思，它深入浅出的讲述了信息在计算机中的表示方式。

通过图像形象生动的展现了底层运算过程中存在的问题。

并在相关知识点最后给出了对应的应用场景和习题令读者加深理解。

以下为本人对本章的学习笔记

思维导图

笔记

2.1、信息存储

2.1.1、字数据大小

定义：每台计算机都有一个字长(word size),指明指针数据的标称大小。

我们常常说一个计算机是32位的、64位的，说的就是计算机的字长。

（我的PC是64位，所以上图代码输出的指针占8个byte，即64位）

而因为32位的二进制有4294967296种状态，即:2³²=4GB。所以32字长的计算机可以控制的虚拟地址上限为4GB。其他字长的计算机可控虚拟地址上限同理可得。

2.1.2、字节顺序

计算机的内存空间划分成若干个连续字节，而我们想表示的数据很多时候不是一个字节就可以表示的。那么对于跨越多个字节的数据或者说对象，组成它的每个字节的存储顺序就有了讨论的必要。

如上图，是0x1234567的两种表示方式。其中：

• 大端法，跟我们人的使用习惯一样。最高有效位在最左边。
• 小端法：则相反，最低有效位在最左边。

这两种表示方法没有优劣之分，这是计算机设计者、生产产商的选择问题。

现今，大多数的Intel兼容机都只用小端，IBM和Oracle的大多数都用大端。

对于偶们程序猿来说，真正需要注意到大、小端问题的，大概也只有当两台采用了不同方案表示字节顺序的机器间进行数据传输时了。不过俗话说，前人栽树后人乘凉，除非要自己定制一套两台机器间的传输标准，不然大概率上我们只需要调用前辈们写好的API就好了。

2.1.3、位级运算

这里讨论的位级运算主要以c语言的位级运算作为例子。

对于任一位向量a，都有$ a \oplus a = 0 $。这是个很有意思的性质，利用这个性质，我们可以玩出很多不同的花样。

例1：交换两个变量

void swap(int *x,int *y){
	*y = *x ^ *y;	//step 1　ｐｐ
	*x = *x ^ *y;	//step 2
	*y = *x ^ *y;	//step 3
}

虽然上述交换两个变量的方式跟普通的利用第三变量交换两个数的方式相比没有性能上的优势，但确实一个见识a^a==0性质作用的一个好例子。

（因为我比较懒，所以没有画图，直接拍照了 dog.jpg）

上图第2步中：

*x = *x ^ *y;
//等价于
*x = a ^ a ^ b;
//根据a^a==0的性质，即：
*x = 0 ^ b == b
//而*y没有变，依然等于a^b

第3步同理可得:*y = a。

---

而让我觉得更有意思的是书上后面紧跟着的练习题2.13

练习题2.13

20世纪七八十年代一种非常流行的机型，没有布尔、and、or指令。只有bis(位设置)和bic(位清除)两个指令。现在，只给我们这bis和bic这两个操作函数，在不能使用任何其他C语言运算的情况下，实现 ”|“或 操作和 ”^“异或 操作。

其中bis和bic具体运算操作和作用如下：

int bis(int x ,int m);	//位设置
int bic(int x, int m);	//位清除
/*
	其中x为输入数据字，m为掩码返回值为z。
	z为x根据掩码m修改后的值。
	
	bis：在m为1的每个位置上，将z对应的位置设置为1。
	bic：在m为1的每个位置上，将z对应的位置设置为0。
*/

实现以下函数：

int bool_or(int x,int y){
    int result = _____________;
    return result;
}

int bool_xor(int x,int y){
    int result = _____________;
    return result;
}

横线处填对应的答案。

分析

对于bis函数：

• 当m的位为1时，z的对应位为1
• 当m的位为0时，z的对应位为x的对应位
  • x的对应位为0或1

由以上分析可得，bis(位设置)其实就是一个或运算。

所以，bool_or函数的空处应该直接写 bis(x,y) 即可。

---

对于bic函数：

• 当m的位为1时，z的对应位为0
• 当m的位为0时，z的对应位为x的对应位
  • x的对应位为0或1

类比对bis函数的分析，我们看看与运算。

当 $ A & B $ 时，我们可以把 $ B $ 看作掩码 $ m $ ,所以对于与运算：

• 当m的位为0时，z的对应位为0
• 当m的位为1时，z的对应位为x的对应位
  • x的对应位为0或1

由上述分析，得到下面式子：

$bis(A,B)\ =\ A\ \& \ \sim B$

可以看出bic函数的本质其实是 与 和 取反 的组合运算！所以对于第二个填空，即要求我们用 或 、 与 和 取反 的组合运算 实现一个异或。

若已经知道异或的与或非表达式的话，就可以直接写出答案了。在这里我们假设不知道异或的 与或非表达式的情况下，类比上面的方式分析推导一下公式。而上述方式其实就是数字逻辑中的利用真值表推出表达式，所以，我们可以得出下图：

由上图，我们可以很清晰的看到 $ A \oplus B $与其他三个式子间的关系。所以我们很容易得到下面的式子：

$A \oplus B\ =\ bic(\ bis(A,B)\ ,\ bis(B,A)\ )$

小结

以上关系推导的最优解法其实是直接列出真值表即可清晰明了的看出各种运算符间的关系表达式。纯数学表达式推导在逻辑运算中不太好使。

2.1.4、移位运算

移位运算没啥东西，需要关注的主要在于右移上。

• 逻辑右移：左端最高位补0
• 算术右移：左端最高位补原最高位的数

而由于为了保证不同机器间代码的可移植性，现在几乎所有编译器都采用算术右移（c语言没有明确规定有符号数应该采用哪种右移方式），所以对于这块只需有个印象即可。

2.2、整数的表示

我们可以把整数的位级表示看成一个 $ ω $ 位的向量 $ \vec{x} $。$ \vec{x} \ =[ x_{ω-1},x_{ω-2},…,x_{0} ]$

2.2.1、无符号整数表示

无符号整数跟正常的非负数的二进制表示一样，为了与后面讨论保持一致性，下面给出无符号整数的数学表达：

$B2U_ω (\vec{x})=\sum_{i=0}^{ω-1}x_i2^i$

其中 $ B2U_ω (\vec{x}) $ 的值为向量 $ \vec{x} $ 的十进制无符号数表示。

结合下图可形象理解。

2.2.2、有符号数表示

有符号数有三种常见的编码表示方式：

• 原码
• 反码
• 补码

其中现在使用最广泛的是补码，其他两种用的不多，原因在后续会给出。

补码编码定义

对于向量$ \vec{x} \ =[ x_{ω-1},x_{ω-2},…,x_{0} ]$：

$B2T_ω (\vec{x})=-x_{ω-1}2^{ω-1}\ +\ \sum_{i=0}^{ω-2}x_i2^i$

其中 $ B2T_ω (\vec{x}) $ 的值为向量 $ \vec{x} $ 的十进制有符号数表示。

图像表示如下：

因为一个整数有正有负，那么我们就需要拿一位来表示这一串01序列表示的数的正负性了。而如果我们随便的指定最高位的0表示负数/正数，1表示正数/负数的话，想让计算机理解是有困难的。所以，我们赋予最高有效一个权值 $ -x_{ω-1}2^{ω-1} $,这样就可以做到 码制和数制的高度统一了。所以最高有效位$ x_{ω-1} $ 也称为符号位。

由上图我们也可以看到这种表示方法的边界是不对称性：$Tmin=-2^{ω-1}$，$ Tmax=2^{ω-1}-1$。

---

未完待续~~~