# CSAPP 第二章笔记

***

## 2. 信息表示法

位是信息储存的基本单位，特指二进制位，储存范围为0\~1。

一个字节固定由8位组成，表示范围是0\~255，与字长（多少位）无关。

### 2.1.1 十六进制

用二进制表示大数过于漫长，所以使用16进制来表示位模式。

十进制： 1-9 10 11 12 13 14 15

十六进制：1-9 A B C D E F

C语言中一般以`0x`或`0X`开头表示十六进制值。

### 2.1.2 字数据大小

计算机系统储存/操作/传送时二进制码的单位称为字。字的长度为字长。

n位机器表示字长为n的机器。如32位和64位。

字长决定了虚拟地址空间的最大大小。32位机器的虚拟地址的范围为 $$0-2^{32}-1$$个字节。

32位和64位程序在编译时编译器分配的字节数是不同的：

|          |      字节数表      |     |     |
| :------: | :------------: | :-: | :-: |
|    有符号   |       无符号      |  32 |  64 |
|   char   |  unsigned char |  1  |  1  |
|   short  | unsigned short |  2  |  2  |
|    int   |  unsigned int  |  4  |  4  |
|   long   |  unsigned long |  4  |  8  |
| int32\_t |    uint32\_t   |  4  |  4  |
| int64\_t |    uint64\_t   |  8  |  8  |
|   float  |                |  4  |  4  |
|  double  |                |  8  |  8  |

### 2.1.3 寻址和字节顺序

不同机器对数据的储存方式不同。

* 小端法（大多数机器）：

最低有效字节储存在低地址，最高有效字节储存在高地址。

* 大端法：

最低有效字节储存在高地址，最高有效字节储存在低地址。

例子 0x012345 在地址0x100-0x102的储存：

小端法：

0x100 0x101 0x102

45 23 01 （其中45是最低有效字节）

大端法：

0x100 0x101 0x102

01 23 45

### 2.1.6 布尔代数

主要是位运算的运算符

* NOT 表示为 \~ 否
* AND 表示为 & 与
* OR 表示为 | 或
* EXCLUSIVE-OR 表示为 ^ 异或

其中 0^1 = 1 而 1^1 != 1

注意位级运算与逻辑运算不同。

### 2.1.9 位移运算

主要是逻辑位移与算数位移的区别。

\[01100011] >>4（逻辑右移）-> \[00000110]

\[01100011] >>4（算数右移）->\[00000110]

\[10010101] >>4（逻辑右移）->\[00001001]

\[10010101] >>4（算数右移）->\[11111001]

第四个运算，因为数据最高位是1，所以用1填充。

### 2.2.2 无符号数的编码

二进制位转无符号数用函数 $$B2U\_\omega$$ （Binary to Unsigned）来表示

无符号数编码的定义：

$$B2U\_\omega(\vec x) = \sum\limits\_{i=0}^{\omega-1}x\_i2^i$$

其实就是将无符号数用二进制位表示。

$$B2U\_\omega$$ 是反身的，即 $$B2U\_\omega$$ = $$U2B\_\omega$$ ，因为二进制位及其表示的数是一一对应的。

### 2.2.3 补码编码

补码（Two's Complement）编码的定义：

$$B2T\_\omega(\vec x) = -x\_{\omega-1}2^{\omega-1}+ \sum\limits\_{i=0}^{\omega-1}x\_i2^i$$

主要逻辑是因为最高有效位为1的值大于其他所有没有该位的数，所以设它的权重为负（$$-2^{\omega-1}$$）。

因为其权重最高，所以当最高有效位为1时，整个数的值必<0；当最高有效位为0时，整个数的值必>0.

例子（$$\omega$$代表补码位数，这里是4位补码）：

$$
B2T\_4(\[0101]) = -0*2^3 + 1*2^2 +0*2^1 + 1*2^0 = 0+4+0+1 = 5
$$

$$
B2T\_4(\[1011]) = -1*2^3 + 0*2^2 +1*2^1 + 1*2^0 = -8+0+2+1 = -5
$$

可以看出，$$\omega$$位补码能表示的最大范围 $$TMax\_\omega = 2^{\omega-1}-1$$ ，其表示的最小范围为$$TMin\_\omega=-2^{\omega-1}$$

以长度4为例，其表示的范围就为 -8\~7.

数字与补码间也是一一对应的，具有反身性。

> 个人补充
>
> 由此可以看出，程序在被编译时需要确定相应类型的最大数据长度（位数），因此才有int\_32或者64之类的标准。此外，这里也说明int空间内所存储的数字大小并不影响其所占用的内存空间。

有符号数还有两种表示方法，即**原码**和**反码**。

从补码展开其实是英文和数学的逻辑（如`Two's Complement`指对非负数x的表示法为$$2^\omega-x$$）。中文的逻辑（如`原码` `补码`）是从原码出发，反码和补码是对原码的修改。

* 原码

原码是人脑比较容易理解的一种表示方法，即在原本数据上再加一个二进制位表示正负，0表示正，1表示负。

例：（8位）

1：\[0000 0001] -1：\[1000 0001]

> 注：
>
> 正数的补码和原码相同，负数就是原码除符号位不变，其他全部与原码相反，最后+1
>
> \[+1] = \[00000001]原 = \[00000001]反 = \[00000001]补
>
> \[-1] = \[10000001]原 = \[11111110]反 = \[11111111]补
>
> 可以理解补码是在反码的基础上补。

* 反码

反码与补码类似，只不过最高位有效权是$$- (2^{\omega-1}-1)$$ 而不是$$-2^{\omega}-1$$。

> 注：
>
> 正数的反码和原码相同，负数的反码除了符号位不变，其他全部与原码相反。
>
> \[+1] = \[00000001]原 = \[00000001]反
>
> \[-1] = \[10000001]原 = \[11111110]反
>
> 可以理解反码是原码基础上的反位结果。

### 2.2.4 有符号数与无符号数的转换

这样的转换在处理时，不改变原来的二进制位值，只是解释的方法改变。

* 补码->无符号数

$$
T2U\_{\omega}(x)=x+2^{\omega} \space\space(x<0)
$$

补码$$-2^{\omega-1}$$到0的部分平移到无符号数$$2^{\omega-1}$$到$$2^{\omega}$$之间，x>0的部分不变。

* 无符号数->补码

$$
U2T\_{\omega}(x)=x-2^{\omega} \space\space(x>TMax\_{\omega})
$$

无符号数$$2^{\omega-1}$$到$$2^{\omega}$$之间的部分平移到补码$$-2^{\omega-1}$$到0之间，x<$$2^{\omega-1}$$的部分不变。

> 补：关于为什么C语言定义INT\_MIN要用-(INT\_MAX)-1而不用-2147483648：
>
> [c语言里面TMin不能写成-2147483648的原因\_zerods-seu的博客-CSDN博客](https://blog.csdn.net/zerodshei/article/details/51920425)

### 2.2.6 扩展一个数的位表示

1. 无符号数的扩展：零扩展（扩展位全部填零）
2. 补码数的扩展：

$$B2T\_{\omega+k}(\[x\_{\omega-1},...,x\_{\omega-1},x\_{\omega-1},x\_{\omega-2},...,x\_0]) = B2T\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])$$

即扩展位都用最高位填充

> 例：\[1011] = 3-8 = -5
>
> \[11011] = 8+3-16 = -5
>
> \[111011] = 16+8+3-32 = -5

### 2.2.7 截断数字

1. 截断无符号数：

有可能不溢出，也可能出现溢出的情况（截断了有效位）。出现溢出时就和通过取余的方法来取减小位数类似：

$$B2U\_k\[x\_{k-1},x\_{k-2},...,x\_0]= B2U\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])\space mod\space 2^k$$

1. 截断补码数：

与截断无符号数类似：

$$B2T\_k\[x\_{k-1},x\_{k-2},...,x\_0]= U2T\_k( B2U\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])\space mod\space 2^k )$$

例子：将四位数值截断到三位数值：

| 二进制  | 二进制 | 十六进制 | 十六进制 | 无符号 | 无符号 | 补码  | 补码  |
| ---- | --- | ---- | ---- | --- | --- | --- | --- |
| 原始值  | 截断值 | 原始值  | 截断值  | 原始值 | 截断值 | 原始值 | 截断值 |
| 0000 | 000 | 0    | 0    | 0   | 0   | 0   | 0   |
| 0010 | 010 | 2    | 2    | 2   | 2   | 2   | 2   |
| 1001 | 001 | 9    | 1    | 9   | 1   | -7  | 1   |
| 1011 | 011 | B    | 3    | 11  | 3   | -5  | 3   |
| 1111 | 111 | F    | 7    | 15  | 7   | -1  | -1  |

### 2.3.1 无符号加法

无符号加法溢出：$$x+y=x+y-2^\omega$$（溢出时）

### 2.3.2 补码加法

补码加法溢出：

$$x+y=x+y-2^\omega$$（正溢出）

$$x+y=x+y+2^\omega$$（负溢出）

### 2.3.4 无符号和补码乘法

无符号和补码的乘法也类似，溢出时截断即可。

$$x\*y = (x ×y)mod\space2^\omega$$

### 2.3.6 乘/除以常数

一个变量乘或除以常数时可以用位移的方法用更快的时间来达到同样的目的（编译器其实也会做类似优化）

$$x\*2^k = x<<2$$

$$x/2^k = x>>2$$

### 2.4.1 二进制小数

小数相对整数不同主要是因为有小数点的定义。但如果使用定点数，即小数点所在的位确定的表示方法来表示小数，其能表示的数将非常有限。

浮点数顾名思义就是小数点所在位不定的表示方法。

### 2.4.2 IEEE浮点表示

IEEE浮点标准用类似科学计数法的方式来表示小数。

例如十进制数12.34可以表示为$$1×10^1+2×10^0+3×10^{-1}+4×10^{-2}$$

同样二进制数10.11可以表示为$$1\times2^1+0\times2^0+1\times2^{-1}+1\times2^{-2}$$

类似科学技术法有 符号S$$（+1/-1）\times 原数M（如1234）\times2^{指数E}$$

**IEEE浮点标准表示法定义：**

$$V = (-1)^s\times M \times 2^E$$

其中：

> S：符号位 0/1
>
> M：尾数 表示一个整数，相当于上述的原数
>
> E：阶码 表示一个整数，作用是为尾数加权 类似于上述2的指数

在具体内存中，float和double数据类型的结构分布为：

符号数（s） 阶码（exp）尾数（frac）

> s、exp、frac这里指符号数、阶码、尾数在浮点数数据类型中的位模式，不是它们的值

在float和double类型中阶码和尾数所占的位数不同。

![位表示](https://img-blog.csdnimg.cn/20210206104342484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MDM3MzU4,size_16,color_FFFFFF,t_70)

IEEE定义了三种情况的值：

1. ***规格化的值***

阶码exp的位模式不全为0（exp!=0）且不全为1时，称这个浮点数为规格化的值。

**阶码的值E**: $$E = e - bias$$

> e指浮点数exp位的值，bias是偏置值，因为E需要能够表示负数，所以减去偏置值使得阶码的值的范围能够与0对称。
>
> bias的值为$$2^{k-1}-1$$ （单精度为127，双精度为1023）

**尾数的值M**：$$M=1+f$$

> f 指的是frac区域的位表示的整数值。在解析时给他+1，目的是为了和非规格化数平滑衔接。

1. ***非规格化的值***

阶码exp的位模式全为0（exp=0）且不全为1时，称这个浮点数为非规格化的值。

非规格化的值用来密集且均匀地表示0和0周围的小数。

**阶码的值E**: $$E = 1 - bias$$

> 这里用1-bias 也是为了和规格化的值平滑连接

**尾数的值M**：$$M=f$$

> 因为本身就用于表示0周围很小的数，所以不需要+1.

1. ***特殊值***

当阶码各位全为1时，这个浮点数表示特殊值。

* 小数域（frac）全为0时，表示无穷，正还是负无穷由符号位决定。
* 小数域为非0时，表示NAN，即Not A Number，用来表示结果不能是实数或者无穷的情况，如计算$$\sqrt{-1}$$、无穷大-无穷大时就会返回NAN。

浮点数具体到位上比较难以理解，但看图即可比较好的明白其构造：

!\[aaaaa]\(CSAPP 第二章笔记.assets/aaaaa.png)

!\[img]\(CSAPP 第二章笔记.assets/MCVX\`I%HS\@MY{BO$$J9D\_PI5.png)

### 2.4.4 舍入

对浮点数进行舍入是由于浮点数的精度是有限的，关于某个数（不一定是无理数或者10进制下小数位很长的数）只能由于其最相近的可表示的数来表示。

* 对于正好处于两个可表示小数值中间的数，IEEE标准采用**向偶数舍入**的方法，即向舍入后最末位为偶数的方向进行舍入。

!\[bbb]\(CSAPP 第二章笔记.assets/bbb.png)

* 对于其他数，向更靠近的那个可表示的浮点数舍入。

### 2.4.5 浮点运算

因为浮点数存在溢出和舍入的情况，所以在浮点运算时容易出现丢失精度的问题。

例如 (3.14+1e10)-1e10的值为0，因为在第一次运算的时候3.14因为精度问题被舍入了。

因此浮点运算往往不具有交换性和结合性，可能会导致一些问题。

> 哎哟终于结束了 挺枯燥的一章 但还是很有意思的（