第2章信息的表示和处理（一）

现代计算机存储和处理的信息都是二值信号，以特定的方式组合二值信号，就能表示有限集合的任意元素。这一章主要研究的就是计算机中的数字表示，即无符号编码、补码编码和浮点数编码。

大多数计算机用字节（8位的块）作为最小的可寻址的内存单位。
每个程序对象，乃至程序本身都是一个字节序列

对于描述位模式而言，常用十六进制来取代过于冗长的二进制表示法，在十六进制下，一个字节的值域为 $00_{16}$ ~ $FF_{16}$

字长，指明了指针数据的标称大小，决定了虚拟地址空间的大小。
对于字长为$w$位的机器而言，虚拟地址的范围为0 ~ $2^w-1$，最多访问$2^w$歌字节。

对象的地址位为所使用字节中最小的地址。
排列表示一个对象的字节有两个通用的规则，即小端法和大端法。

地址	0x100	0x101	0x102	0x103
大端法	01	23	45	67
小端法	67	45	23	01

C语言中，字符串被编码为一个以null字符结尾的字符数组。

不同机器类型使用不同且不兼容的指令和编码方式，故二进制代码不兼容。

位向量可以很好的表示有限集合。将所有元素有序排列后，任意由这些元素组成的集合，均可用位向量表示，0代表不具有该元素，1代表具有该元素。而在这样的表示方法中布尔代数可以方便地处理集合运算，|对应集合的并，&对应集合的交，~对应集合的补集。

C语言支持按位布尔运算。

只需注意一下C语言中逻辑运算具有短路效应，也就是说对于&&和||，如果第一个参数求值就能确定表达式的结果，那么第二个表达式就不会计算。

2.1.9 C语言中的移位运算

左移运算：操作符<<，例如x<<k，代表x向左移动k位，丢弃最高的k位，并在右端补k个0。
右移运算：操作符<<，例如x<<k，代表x向右移动k位。但是右移一般右两种：逻辑右移和算数右移。逻辑右移是在左边补k个0，算数右移是在左端补k个最高有效位。
几乎所有编译器对有符号数使用算数右移，对无符号数，右移是逻辑的。

本节介绍用位编码整数的两种方式

C语言标准定义了每种数据类型必须能够表示的最小的取值范围。但是通常实际会比标准大上一些

对于一个$w$位的整数数据类型，不妨将其看作一个位向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$。将其视为一个二进制数就得到了无符号表示。
定义一个函数$B2U_w$（Binary to Unsigned，长度为w），用来表示由二进制转化为无符号数。

无符号数编码的定义
对向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$
$$B2U_w(\vec x) \doteq \sum_{i=0}^{w-1}x_i2^i$$

在补码的定义中将最高有效位解释为负权。
定义函数$B2T_w$（Binary to Two’s-complement，长度为w），用来表示二进制转补码。

补码编码的定义
对向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$
$$B2T_w(\vec x) \doteq -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2}x_i2^i$$

最高有效位$x_{w-1}$也被成为符号位，为1时，表示值为负，为0时，表示值为非负。

C语言中，强制类型转换保持位值不变，只改变解释这些位的方式。

补码转换为无符号数
对满足$TMin_w \leq x \leq TMax_w$的x有：
$$T2U_w(x) = \begin{cases}x + 2^w, & x < 0 \\ x, & x \geq 0 \end{cases}$$

比较粗略地说，将一个有符号数映射为相应地无符号数时，非负数保持不变，负数被转换为大正数。

同样的，考虑无符号数转换为补码

无符号数转换为补码
对满足$0 \leq u \leq UMax_w$的u有：
$$U2T_w(u) = \begin{cases}u, & u \leq TMax_w \\ u-2^w, & u > TMax_w \end{cases}$$

将一个无符号数映射为相应的有符号数，比较小的数保持不变，比较大的数变成负数。

C语言中，当执行运算时，一个运算数为有符号，另一个为无符号，C语言会隐式地将有符号数转换为无符号数。

无符号数的零扩展：只要将高位用0填充即可。
补码数的符号扩展：只要将高位用符号位填充即可。

截断一个数字，会直接丢弃高位，所以很可能会改变原来的值。