深入理解计算机系统-信息的表示和处理

2.1 信息存储

大多数计算机使用8位的块，或者字节，作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。

内存的每个字节都由一个唯一的数字来表示，称为它的地址，所有可能地址的集合就称为虚拟地址空间。顾名思义，虚拟地址空间只是一个展现给机器级程序的概念性映像，实际的实现是将动态随机访问存储器（DRAM）、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来。

2.1.1 十六进制表示法

一个字节由8个位（bit）组成，在二进制表示法中，它的值域是 $00000000_{2}-11111111_{2}$ ，如果看成十进制整数，值域为 $0_{10}-255_{10}$ ，两种表示方法都不是非常方便，二进制表示太冗长，十进制表示与位模式的互相转化很麻烦。代替的方法是，以16为基数（16进制数）表示位模式。

十六进制使用数字‘ 0 ’ ~ ‘ 9’ 以及字符 ' A ' ~ ' F ' 来表示16个可能的值，一个字节的值域为 $00_{16}-FF_{16}$

在C语言中，以 0x 或 0X 开头的数字常量被认为是十六进制的值。

十六进制表示法

① 二进制与十六进制的转换简单直接：

例如：0xFa1D37b，将该十六进制转化为二进制，为 1111 1010 0001 1101 0011 01111 1011

将十六进制的每一位各自转化成长度为4的二进制，然后按照顺序排列在一起即可（二进制转化十六进制同理）

十六进制	F	a	1	D	3	7	b
二进制	1111	1010	0001	1101	0011	0111	1011

将二进制数转化为十六进制数， 11 1100 1010 1101 1011 0011转化为16进制 3CADB3

把其分为每4位为一组来转化，若总数不是4的倍数，前面用0补齐即可

二进制	0011	1100	1010	1101	1011	0011
十六进制	3	C	A	D	B	3

当 x 是 2 的非负整数 n次幂时，即 $x=2^{n}$ ，很容易地将 x 写成十六进制形式，只要记住 x 的二进制表示就是 1 后面跟 n 个 0，十六进制数字 0 代表 4 个二进制数字 0，所以即 x=i+4j 的形式，其中 i 在 0~3 之间， 把 x 写成开头的十六进制数字为 1(i=0)，2(i=1)，4(i=2)，8(i=3) ，随后跟 j 个十六进制的 0。例如 x=2048=2^11 11=3+3*4，则十六进制表示为 0x8000

② 十进制与十六进制的转换

使用乘法或者除法来处理一般情况

将一个十进制数字x转化成十六进制，反复除以16，得到商 q 和余数 r， x=q*16+r，然后用十六进制数字表示的 r 为最低为数字，并且通过对 q 反复进行该过程得到剩下的数字。

例如：314156 的转换

314156 / 16 = 19634 余 12 （C）

19634 / 16 = 1227 余 2 （2）

1227 / 16 = 76 余 11 （B）

76 / 16 = 4 余 12 （C）

4 / 16 = 0 余 4 （4）

最终，十六进制为 0x4CB2C （从下往上，因为越往后的位数越高）

2.1.2 字数据大小

每台计算机都有一个字长，指明指针数据的标称大小。字长决定了虚拟地址空间的最大大小，即对于一个字长为 w 位的机器而言，虚拟地址的范围为 $0-2^{w}-1$ ，程序最多访问 $2^{w}$

C语言中，支持整数和浮点数多种数据格式，如图各种数据类型分配的字节数，

大部分数据类型都编码为有符号数值，除非有前缀关键字 unsigned 或对确定大小的数据类型使用了特定的无符号声明。数据类型 char 是一个例外，尽管大多数编译器和机器将他们视为有符号数，但 C标准不保证这一点。

大多数 64 位机器也可以运行为 32位机器编译的程序，这是一种向后兼容。因此，当程序 prog.c 用如下伪指令编译 linux>gcc -m32 prog.c 该程序就可以在 32位或 64位机器上正确运行。另一方面，若程序用下面伪指令编译 linux> gcc -m64 prog.c 那就只能在 64位机器上运行。因此，将程序称为 “ 32 位程序 ” 或 “ 64位程序 ”，区别在于该程序是如何编译的，而不是其运行的机器类型。

2.1.3 寻址和字节顺序

对于跨越多字节的程序对象，建立两个规则：该对象的地址是什么，以及在内存中如何排列这些字节。 在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。 例如，假设一个类型为 int 的变量 x 的地址为 0x100（地址表达式的值 &x为 0x100），那么x（32位表示）的四个字节将被存储在内存的 0x100，0x101，0x102，0x103位置。

考虑一个 w 位的整数，其位表示位 $[x_{w-1},x_{w-2},....,x_{2},x_{1},x_{0}]$ ，其中 $x_{w-1}$ 是最高有效位，x0是最低有效位。若 w 是 8 的倍数，这些位就能被分组成为字节，

最高有效字节包含位 $[x_{w-1},x_{w-2},x_{w-3},x_{w-4},x_{w-5},x_{w-6},x_{w-7},x_{w-8}]$

最低有效字节包含位 $[x_{7},x_{6},x_{5},x_{4},x_{3},x_{2},x_{1},x_{0}]$

某些机器选择在内存中按照最低有效字节到最高有效字节的顺序存储对象（小端法），另一种则按照从最高有效字节到最低有效字节的顺序存储（大端法）。

假设变量 x 的类型为 int，位于地址 0x100处，其十六进制值为 0x01234567，地址范围0

x100~0x103的字节顺序依赖机器的类型 高位字节值为 0x01 低位字节值为0x67 （16进制）

大端法（由高到低）

	0x100	0x101	0x102	0x103
	01	23	45	67

小端法（由低到高）

	0x100	0x101	0x102	0x103
	67	45	23	01

对于如下汇编代码表示：

4004d3: 01 05 43 0b 20 00 add %eax,0x200b43(%rsp)

这一行由反汇编器生成，意思是十六进制字节串 01 05 43 0b 20 00 是一条指令的字节级表示，这条指令是把一个字长的数据加到一个值上，该值的存储地址由 0x200b43 加上当前程序计数器的值得到的，当前程序计数器的值即为下一条将要执行指令的地址。如果取出这个序列的最后四字节: 43 0b 20 00，并按照相反的顺序写出 00 20 0b 43.去掉开头的 0，得到值 0x200b43，就是右边的数值。

2.1.4 表示字符串

C语言中字符串被编码为一个以null（值为0）字符结尾的字符数组，每个字符都由某个标准编码来表示，最常见的是 ASCII 字符码。

例如，以参数 “ 12345 ” 和终止符来运行历程 show_bytes，得到的结果 31 32 33 34 35 00。注意：十进制数字 x 的 ASCII 码正好是 0x3x，而终止字节的十六进制表示为 0x00.

2.1.5 表示代码

不同的机器类型使用不同的且不兼容的指令和编码方式，即使是完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。

在机器的角度，程序0000000仅仅只是字节序列，机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表意外。

2.1.6 布尔代数简介

二进制值是计算机编码，存储和操作信息的核心。

最简单的布尔代数是在二元集合{0，1}基础上的定义，定义布尔代数中的几种运算。

① ~ (逻辑运算 NOT ) 取反运算，即 ~0=1 ，~1=0 对每一位数都取反

② & （逻辑运算 AND），∩ ，两者为真（1）才为真（1），其余都是假（0）

③ | （逻辑运算 OR），或，两者只要有一真（1）即为真（1），二者都为假(0)才为假(0)

④ ^ （逻辑运算异或）二者为真（1）但不同时为真（1）时，结果才为真（1）

将上述四个布尔运算拓展到位向量的运算，固定长度为 w，由 0 和 1 组成的串，进行上述规则的运算。

位向量一个很有用的应用就是表示有限集合。可以用位向量 $[a_{w-1},a_{w-2},......,a_{2},a_{1},a_{0}]$ 编码任何子集 $A\subseteq \left \{ 0,1,2.....,w-1 \right \}$ ，其中 $a_{i}=1$ 当且仅当 $i\in A$ .

例如位向量 a=[01101001] 表示集合 A={0,3,5,6} ,位向量 b=[01010101] 表示集合 B={0,2,4,6}

使用这种编码集合的方法,布尔运算 | 和 & 分别对应于集合的并和交, ~ 对应于集合的补

运算　a&b =[01000001] , 而 A∩B={0,6}

2.1.7 C语言中的位级运算

位级运算的一个常见用法就是实现掩码运算，掩码是一个位模式，表示从一个字中选出的位的集合．

掩码 0xFF (最低的８位为１)表示一个字的低位字节，位级运算 x&0xFF 生成一个由x的最低有效字节在值，而其他的字节就被置为 0。例如：x=0x89ABCDEF，表达式最后结果为 0x000000EF，表达式~0将生成一个全1的掩码，不管机器的字大小多少。

位设置（bis）与位清除（bic），两种指令的输入都是一个数据字x和一个掩码字 m

位设置（bis）：生成一个结果 z，z是根据掩码 m 的位来修改 x 的位得到的，就是在m为1的每个位置上，将 z 对应的位设置为 1 （x|m）仅在 x 和 m 都为0 的情况下为0。

位清除（bic）：结果z就是在m为1的每个位置，将z对应的位设置为0 (x&~m) 仅在 x为1 m为0 的情况下结果为 1

位设置和位清除实现布尔运算：

① | and 运算： bis (x,y)

② ^ 异或运算： bis(bic(x,y),bic(y,x))

2.1.8 C语言中的逻辑运算

C语言中的逻辑运算有：|| , && . ! 分别对应命题逻辑中的 OR AND NOT 运算。逻辑运算认为所有非零的参数都表示 TRUE，返回 1，而参数 0 表示 FALSE

观察到，只有参数被限制为0 1 时，才进行逻辑运算

逻辑运算符&& || 和他们对应在位级运算 & | 的区别，如果第一个参数求值能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值．

①　ａ＆＆５／ａ

a && 5/a 表达式首先检查 a 是否为“真”，如果不是，则表达式结果立即确定为 false。

如果 a 为“真”，则已经确保 a 不为0，不会发生除以零的错误

②　ｐ＆＆＊ｐ＋＋

如果 p 不是空指针（即 p 不等于 NULL 或者 nullptr），那么 p 的布尔值为 true。

如果 p 是空指针，整个表达式的值将直接是 false，并且不会执行后续的 *p++ 部分。

2.1.9 C语言中的移位运算

对于一个位表示 $[x_{w-1},x_{w-2},,,,,x_{1},x_{0}]$ 的操作数，表达式Ｘ＜＜ｋ会生成一个值，其位表示 $[x_{w-k-1},x_{w-k-2},,,,,x_{1},x_{0},0,,,,,0]$ ，也就是说，ｘ向左移动ｋ位，丢弃最高的ｋ位，并在右端补ｋ个０.

对应的右移运算ｘ＞＞ｋ，一般而言，机器支持两种右移：逻辑右移，算数右移

逻辑右移：在左端补ｋ个０，得到的结果为 $[0,,,,,0,x_{w-1},x_{w-2},,,,,x_{k+1},x_{k}]$

算术右移:在左端补 k 个最高有效位的值,得到结果为 $[x_{w-1},,,,x_{w-1},x_{w-1},x_{w-2},,x_{1},x_{0}]$

C语言没有明确规定使用移位过程中是逻辑右移还是算术右移，但是几乎所有的编译器/机器组合都对有符号数使用算术右移。

与C相比，Java对于如何进行右移有明确的定义。表达式x>>k会将x算术右移k位，而x>>>k会对x做逻辑右移。

2.2 整数表示

2.2.1 整型数据类型

C语言支持多种整型数据类型——表示有限范围的整数.

①同时,被表示的数字是非负数(声明为 unsigned), 32位机器和 64位机器在 long 中不同.

②另外,负数与正数的不确定性,负数的范围比正数大1

2.2.2 无符号数的编码

有一个整数数据类型有w位，将位向量写成 $\overrightarrow{x}$ ,表示整个向量，或写成 $[x_{w-1},x_{w-2},,x_{1},x_{0}]$ 表示向量中的每一位. 把 $\overrightarrow{x}$ 看成一个二进制表示的数，得到 $\overrightarrow{x}$ 的无符号表示.

在该编码中,每个位 $x_{i}$ 都取值 0 或 1，后一种取值意味着数值 $2^{i}$ 应为数字值的一部分,用一个函数 $B2U_{w}$ 来表示.(二进制到无符号数)

无符号数编码的唯一性: 每个介于 $0\rightarrow ~2^{w}-1$ 之间的数都有唯一一个w位的值编码与其对应

函数B2Uw是一个双射。即，反过来，我们称其为U2Bw（无符号数到二进制），每一个整数都可以映射为一个唯一的长度为 w 的位模式。

2.2.3 补码编码

最高有效位解释为负权,用 $B2T_{w}$ ( 长度为 w ) 表示

最高有效位 $x_{w-1}$ 为符号位,其权重为 $-2^{w-1}$ ,是无符号表示中权重的负数.

当符号位为 1 时 , 表示值为负 , 而当设置成 0 时 , 值为非负

考虑 w 位补码所能表示值的范围

①符号位为1 , 根据定义公式,当[10,,,00]时,取得最小值 $-2^{w-1}$

②符号位为0 , 即当为[0111,,,11]时,取得最大值 $\sum_{i=0}^{w-2}2^{i}=2^{w-1}-1$

补码编码的唯一性:可表示数的范围内的每个数字都有一个唯一的w位的补码编码

函数B2Tw是一个双射。函数T2Bw（补码到二进制）作为B2Tw的反函数。

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

C语言允许在各种不同的数字数据类型之间做强制类型转换。表达式（unsigned）x会将x的值转换成一个无符号数值，(int) x会将x装换成一个有符号数值。

考虑以下代码

short int v=-12345;

unsigned short uv=(unsigned short) v;

printf("v=%d, uv=%u \n",v,uv);

输出的结果为: v=-12345, uv=53191

可以得出 强制类型转换的结果保持位值不变, -12345的16位补码表示与 53191的16位无符号表示是完全一样的,将short强制类型转换为 unsigned short 改变数值,不改变位表示

定义函数 $U2B_{2} , T2B_{2}$ , 他们将数值映射为无符号数和补码形式的位表示,也就是说：

① 给定 $0\leq x\leq UMax_{w}$ 范围内一个整数，函数 U2Bw(x)会给出 x 的唯一的w位无符号表示。

② 给定 $TMin_{w}\leq x\leq TMax_{w}$ ，函数T2Bw(x)会给出 x 的唯一的w位补码表示。

现在将函数 $T2U_{w}$ 定义为 $T2U_{w}(x)\doteq B2U_{w}(T2B_{w}(x))$ ，补码（T）转化成无符号数（U），即为补码先转换成二进制，再由二进制转化为无符号数。

定义函数 $U2T_{w}(x)$ 为 $U2T_{w}(x)\doteq B2T_{w}(U2B_{w}(x))$ ，与上同理。

变换规则：只改变数值，位表示不变。

T2Uw(x)（补码转换成无符号数）

推导过程：

首先把x转换成二进制表示，若为正，其最高位为0，则值与无符号数相同；若为负，其最高位为1，则无符号数的值与补码的值相差了最高位的2倍，即为 $2*2^{w-1}=2^{w}$ ，其余位数与无符号数相同，则最终值为 $x+2^{w}$

U2Tw(x)（无符号数转换成补码）

推导过程，与上同理：

首先将无符号的值转化成二进制表示，若未超出补码的最大值，则最高位上为0，与补码值相同；若超出补码的最大值，则对应最高位为1，取负，相当于二者差了最高位2倍，则减去 $2^{w}$ ，最终值为 $x-2^{w}$

2.2.5 C 语言中的有符号数与无符号数

C语言支持所有整型数据类型的有符号和无符号运算，但几乎所有的机器都使用补码，因此大多数数字都是默认为有符号的。例如，声明一个像12345的常量时，这个值被默认为有符号的，若要创建一个无符号常量，必须加上后缀字符 ‘ U ’ 或者 ‘ u ’，例如 12345U。

当用 printf 输出数值时，分别用指示符%d，%u，%x以有符号十进制，无符号十进制，十六进制格式输出一个数字，注意 printf 没有使用任何类型信息，所以可以用 %u 输出类型为 int 的数值，也可以用%d 输出类型为 unsigned 的数值

int x = -1;

unsigned u=2147483648; // 2的31次方

printf(" x = %u = %d\n",x,x);

printf(" u = %u = %d\n",u,u);

当在一个 32 位机器上运行时，输出如下：

x = 4294967295 = -1

u = 2147483648 = -2147483648

运行转换函数 $T2U_{32}(-1)=2^{32}-1 \, \, \, \, \, \, \,, U2T_{32}(2^{31})=2^{31}-2^{32}=-2^{31}$

当执行一个运算时，它的一个运算数是有符号的而另一个是无符号的，那么C语言会默认地将有符号数强制转换成无符号数，并假设两个数都是非负的，来执行这个运算。

例如 -1<0U ，因为第二个参数为无符号数，则第一个参数隐式转化为无符号数，T2U（-1）=B2U（111.....1(32个1)）

2.2.6 扩展一个数字的位表示

无符号数转换为一个更大的数据类型，只需要简单的在表示的开添加零，称为零扩展

补码数转换为一个更大的数据类型，可以执行一个符号扩展，在表示中添加最高有效位的值。

当数值为正时，即补码符号位为 0 ，进行零扩展即可。

当数值值为负时，即补码符号位为 1 ，则在其前面添加的有效位全为 1 .

举例说明（以负数为例）：

补码为 [101] 对应值为 -4+1=-3，对其进行符号扩展至 4位，[1101] 对应值为 -8+4+1=-3

数值为负，补码值符号扩展符号位1的解释：

补码到数值的计算，符号位的计算为 $(-1)*2^{w-1}$ ，扩展位表示需要保持数值不变，而符号位会根据扩展发生改变，原符号位的(-1)变成正值，因此需要将差值补齐。例如扩展2位，原本的符号位1则变成正值，与原先值相差 $2^{w}$ ，再将其前一位补1，则相差 $2^{w+1}$ ，即恰好与最高有效位上的1抵消，从而保持数值不变。（扩展多位同理）

在补码中 [111] 与 [1111]，都对应数值的 -1 .

2.2.7 截断数字

如果不用额外的位来扩展一个数值，而是减少表示一个数字的位数，这可能会改变它的值（溢出的一种形式）。

对于一个无符号数，很容易得出其数值结果，就是取模运算，将 k 位前的数都截断为0（与右移不同除法运算）。

补码的截断与之类似，只需要将最高位转换成符号位即可，也有是无符号数转化为补码形式

先将补码的二进制转换成无符号数值形式，再进行截断（取模），最后再将无符号数值转换成补码形式（数值发生改变），或者理解为与无符号一样直接取模。（最好先确定符号位，比如有符号数截断后首位为符号位）

2.3 整数运算

2.3.1 无符号加法

考虑 w 位的参数x，y，定义加法运算， $0\leq x,y< 2^{w}$ ，存在某种情况，使得 $x+y\geq 2^{w}$ 从而产生溢出，对于其位级表示，只需要简单的截断溢出部分（即 $mod \, \, 2^{w}$ ），就相当于减去 $2^{w}$

检测无符号数加法的溢出：对在范围 $0\leq x,y\leq UMax_{w}$ 中的 x 和 y，令 $s = x+_{w}^{u}\textrm{y}$ ，对计算 s ，当且仅当（s<x 或者 s<y）时，产生溢出。

无符号数求反

2.3.2 补码的加法

在给定范围 $-2^{w-1}\leq x,y\leq 2^{w-1}-1$ 之内的整数值 x，y，它们的和就在范围 $-2^{w}\leq x+y\leq 2^{w}-2$ 之内的整数值 x 和 y，要想准确表示，可能需要 w+1位，与前面类似，需要截断到 w 位，从而避免数据大小的不断扩张。

当正数超出 $2^{w-1}-1$ ，通过 $-2^{w}$ 截断，当负数低于 $-2^{w-1}$ ，则需要 $+2^{w}$

既然补码加法与无符号数加法有相同的位级表示，可以按照如下步骤运算补码加法，将其参数转换为无符号数，执行无符号数加法，再将结果转换为补码（直接通过无符号数相加后截断，再转换为补码）

检测补码加法中的溢出

对满足 $TMin_{w}\leq x,y\leq TMax_{w}$ 的 x,y，令 $s=x+_{w}^{t}\textrm{y}$ ，当且仅当 x>0,y>0，但 $s\leqslant 0$ 时，s发生正溢出；当且仅当 x<0，y<0，但 $s\geq 0$ 时，发生负溢出。

2.3.3 补码的非

范围在 $TMin_{w}\leq x \leq TMax_{w}$ 中的每个数字 x 都有 + $_{_{w}^{t}\textrm{}}$ 的加法逆元，如下表示 $-_{w}^{t}\textrm{}$

对于 w 位的补码加法而言， TMinw是自己加法的逆，而对于其他数值，都有 -x 作为其加法的逆。

2.3.4 无符号乘法

范围在 $0\leqslant x,y\leqslant 2^{w}-1$ 内的整数x，y可以表示为 w 位的无符号数，但乘积 x*y的范围在 $0\rightarrow \left ( 2^{w}-1 \right )^{2}=2^{2w}-2^{w+1}+1$ 之间，可能需要 2w 位来表示。 C语言中无符号乘法被定义为产生 w 位的值，就是 2w 位的整数乘积的低 w 位表示的值。表示为 $x*_{w}^{u}\textrm{y}$

将一个无符号数截断为w位等价于计算该值模 $2^{w}$

2.3.5 补码乘法

范围在 $-2^{w-1}\leqslant x,y\leqslant 2^{w-1}-1$ 内的整数x，y可以表示为 w 位的补码数字，乘积 x*y的范围在 $-2^{w-1}*(2^{w-1}-1)=-2^{2w-2}+2^{w-1}$ 到 $-2^{w-1}*-2^{w-1}=2^{2w-2}$ ，用补码表示需要 2w 位

将一个补码数截断为w位等价于计算该值模 $2^{w}$ ，再将无符号数转化成补码形式

无符号和补码乘法的位级等价性：

给定长度为 w 的位向量 $\underset{x}{\rightarrow},\underset{y}{\rightarrow}$ ，用补码形式的位向量表示来定义整数 x，y

$x=B2T_{w}(\underset{x}{\rightarrow}),y=B2T_{w}(\underset{y}{\rightarrow})$ ，用无符号形式的位向量表示来定义非负整数 x',y' $x'=B2U_{w}(\underset{x}{\rightarrow}),y'=B2U_{w}(\underset{y}{\rightarrow})$ ，则 $T2B_{w}(x*_{w}^{t}\textrm{y})=U2B_{w}(x'*_{w}^{t}\textrm{y'})$

位级等价性说明：对于每一对位级计算数，执行无符号和补码乘法，得到的 6 位乘积，再将这些乘积截断到 3 位，无符号截断后的乘积总是 mod 8，虽然无符号和补码两种乘法的乘积的 6 位表示不同，但截断后的乘积的位级表示都相同（值不相同）。

位级等价性推导：可知 x，y 与 x'，y‘ 的关系， $x'=x+x_{w-1}*2^{w}, y'=y+y_{w-1}*2^{w}$ ，这些值的乘积模 $2^{w}$ ，得到

① $(x'*y')\, mod\,2^{w}=[(x+x_{w-1}*2^{w})*(y+y_{w-1}*2^{w})]\, mod \, 2^{w}=(x*y)\, mod\, 2^{w}$ ------->

② $T2U_{w}(x*_{w}^{t}\textrm{y})=T2U_{w}(U2T_{w}(x*y)\, mod\, 2^{w})=(x*y)\, mod\, 2^{w}$ --------->

③ $T2U_{w}(x*_{w}^{t}\textrm{y})=(x'*y')\, mod\, 2^{w}=x'*_{w}^{t}\textrm{y'}$

等式③ 应用 U2Bw 得 $U2B_{w}(T2U_{w}(x*_{w}^{t}\textrm{y}))=T2B_{w}(x*_{w}^{t}\textrm{y})=U2B_{w}(x'*_{w}^{u}\textrm{y'})$

2.3.6 乘以常数

乘法指令的执行需要多个时钟周期，因此编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。

首先考虑乘以 2 的幂 $2^{k}$

即向左移 k 位，若出现溢出情况，则舍去超出部分的位数

由于整数乘法比移位和加法的代价大得多，因此编译器试图以移位，加法和减法的组合来消除很多整数乘以常数的情况。例如，假设一个程序表达式为 x * 14 ，那么编译器则会以 $14=2^{3}+2^{2}+2^{1}$ 的形式进行计算，将乘法写为 $(x<<3)+(x<<2)+(x<<1)$ ，变为三个移位和两个加法，此外还可以以 $14=2^{4}-2^{1}$ 形式，将乘法写为两个移位和一个减法。

对于某个常数K，表达式 x*K，生成代码，编译器会将 K 的二进制表示表达为一组 0 1 交替的序列 $[(0..0)(1..1)....(1..1)(0..0)]$ ，考虑一组从位置 n 到位置 m 的连续的 1 （n>=m），可以用两种不同的形式表述：

形式①： $(x<<n)+(x<<(n-1))......+(x<<m)$

形式②： $(x<<(n+1))-(x<<m)$

2.3.7 除以 2 的幂

整数除法比乘法更慢，需要30个或者更多的时钟周期，除以 2 的幂也可以用移位运算来实现，与上面不同的是使用右移，此外，无符号和补码运算分别使用逻辑移位和算术移位达到目的。

① 除以 2 的幂的无符号除法（逻辑移位）

C 变量 x 和 k 有无符号数值 x 和 k，且 $0\leqslant k< w$ ，则表达式 x>>k 产生数值

即简单的逻辑移位，右移 k 位，若出现小数（右移舍去的位置上出现1）直接舍去。

除以 2 的幂的补码运算，情况稍微复杂，为了保证负数仍然为负，移位执行算术移位。

② 除以 2 的幂的无符号除法（算术移位）

C 变量 x 和 k 分别有补码值 x 和无符号数值 k，且 $0\leqslant k< w$ ，当执行算数移位时，C表达式 x>>k 产生数值

对于 $x\geq 0$ ，最高有效位为0，效果和逻辑右移一样。

当考虑负数时，出现不同。当不需要舍入的情况，结果是 $x/2^{k}$ ；当需要舍入时，移位导致结果需要向下舍入，例如 当结果为 -771.25 时，向下舍入后为 -772，需要调整处理负数 x 的除法。

通过加上 $2^{k}-1$ ，会出现两种情况，

①除去后低k位不加1，即舍去的k位全部为0，无影响。

② 除去后低k位出现加1，此时结果就可以向零舍去。

2.4 浮点数

2.4.1 二进制小数

十进制表示法使用有如下表示 $d_{m}d_{m-1}d_{m-2}...d_{1}d_{0}.d_{-1}d_{-2}...d_{-n}$ 每个十进制dm的取值范围为 0~9，则一个十进制表示为 $d=\sum_{i=-n}^{m}10^{i}*d_{i}$

数字权的定义与十进制小数点符号（.）有关，在小数符号左边为 10 的正幂，右边为 10 的负幂。

类似，考虑二进制小数表示 $b_{m}b_{m-1}...b_{1}b_{0}.b_{-1}b_{-2}...b_{-n}$ ，则每个 bi 取值在 0~1，则该表示方法下的数为 $b=\sum_{i=-n}^{m}2^{i}*b_{i}$

当考虑有限长度的编码，十进制表示法不能准确的表达 1/3 5/7 这样的小数，同样，小数的二进制表示法只能表示那些能够被写成 $x*2^{y}$ ，其他值只能被近似表示，此外，增加二进制表示的长度可以提高其精度。

2.4.2 IEEE 浮点表示

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

① 符号s （sign）决定是负数（s=1）还是正数（s=0），当数值为 0 时作特殊考虑。

② 尾数M 是一个二进制小数，他的范围是 1 ~ 2-e，或者是 0 ~ 1-e

③ 阶码E 的作用是对浮点数加权，权重是 2 的 E 次幂（可能是负数）

将浮点数的位表示划分为三个字段，分别对这些值编码：

① 一个单独的符号位 s 直接编码符号 s

② k 位的阶码字段 exp= $e_{k-1}...e_{1}e_{0}$ 编码阶码 E

③ n 位小数字段编码 frac= $f_{n-1}f_{n-2}....f_{1}f_{0}$ ，编码尾数 M，但是编码出来的值也依赖于阶码的值是否为 0

给定位表示，根据 exp 的值，被编码的值可以分为三种不同的情况（最后一种为两个变种），对单精度格式考虑。

① 规格化的值

最普遍的情况，exp 的位模式既不全为 0 ，也不全为 1 （单精度数值255，双精度数值2047），都属于这种情况。在此情况，阶码字段被解释为以偏置形式表示的有符号整数，也就是说，阶码的值是 E=e-Bias，其中 e是无符号数，位表示为 $e_{k-1}...e_{1}e_{0}$ ，而 Bias是一个等于 $2^{k-1}-1$ （单精度为 127，双精度为1023）的偏置值，由此产生指数的取值范围，单精度 -126~+127，双精度是 -1022~+1023。

小数字段 frac 被解释为描述小数值 f，其中 $1\leqslant M<2$ ，其二进制表示为 $0.f_{n-1}...f_{1}f_{0}$ ，也就是二进制小数点在最高有效位的左边。尾数定义为 M=1+f，有时，这种表示方式叫做隐含的以 1 开头的表示，把 M 看成一个二进制表达式为 $1.f_{n-1}...f_{1}f_{0}$ 的数字。既然我们总是能调整编码E，使得尾数 M 在范围 $1\leqslant f< 2$ 中，那么这种表示方法是一种轻松获得额外精度位的技巧，第一位总是1，不需要显式的表示。

② 非规格化的值

当阶码域全为 0 时，所表示的数是非规格化形式，在此情况下，阶码值是 E=1-Bias（这里与上面比多1），而尾数的值是 M=f，即为小数字段的值，不包含的开头的1。

非规格化有两个用途，①它提供了一种表示数值0的方法，因为使用规格化数，必须总是使 $M\geq 1$ ，无法表示 0 ，实际上，+0.0的浮点表示的位模式为全 0 ，阶码字段全为 0（表明是非规格化值），小数域也全为 0 ，这样就得到 M=f=0，令人奇怪的是，当符号位为1，其他域全为0时，得到值-0.0。根据IEEE的浮点表示，该两种值在某些方面被认为是不同的，而其他方面是相同的。 ② 表示那些非常接近于 0.0 的数，提供了一种属性，称为 逐渐下溢，其中，可能的数值均匀地接近于 0.0

③ 特殊值

①阶码域全为 1 的时候出现的，当小数域全为0，得到的值表示无穷，当 s = 0时是正无穷，s=1时是负无穷，当把两个非常大的数相乘，或者除以0，无穷能表示溢出的结果，②小数域为非零时，结果值为 “NaN”，即不是一个数，一些运算结果不能是实数或者无穷，就会返回 NaN值

2.4.3 数字实例

假定 6 位的格式表示，有 k = 3 的阶码位和 n=2 的尾数位，偏置量是 $2^{3-1}-1=3$ ，图中的 a 部分显示了所有可表示的值（除NaN），两个无穷值在两个末端，最大数量值的规格化数是+-14，非规格化数聚集在 0 的附近，图b部分表示-1.0~1.0之间的数值。

数字的具体实例（8位浮点数格式：1符号 4阶码 3尾数）

对于有 k 位阶码和 n 位小数的浮点表示的一般属性：

① 值 +0.0 总有一个全为 0 的位表示

② 最小的正非规格化值的位表示，最低有效位为1，其他所有位均为 0 构成（0 0...0 0...01）。阶码值为 $E=1-bias=1-(2^{k-1}-1)=2-2^{k-1}$ ，尾数为 $M=f=2^{-n}$ ，因此其数字值为 $V=2^{-n-2^{k-1}+2}$

③ 最大的非规格化值的位表示，阶码字段全为 0，小数字段全为 1（0 0...0 1...1），则 $M=f=1-2^{-n}$ ，则数字值为 $V=(1-2^{-n})*2^{-2^{k-1}+2}$ ，这仅比最小的规格化值小一点。

④最小的正规格化值的位表示，阶码字段最低有效位为1，其余所有字段全为0 （0 0...01 0...0），则阶码值 $E=e-bias=2-2^{k-1}$ ，尾数 $M=1$ ，所以数字值为 $V=2^{-2^{-1}+2}$

⑤ 值1.0的位表示，阶码字段除了最高有效位为0，其他全为1，尾数字段全为 0（0 01....1 0...0）因此 M=1 E=0。

⑥ 最大的规格化值的为表示，符号位为0，阶码的最低有效位为0，其他所有（包括尾数字段）全为1 （0 1..10 1...1） $f=1-2^{-n}\, \, \, \, M=2-2^{-n}$ ， $E=2^{k-1}-1\, \, \, \, \, \, V=(2-2^{-n})*2^{2^{k-1}-1}=(1-2^{-n-1})*2^{2^{k-1}}$

2.4.4 舍入

对于值 x，由于表示方法限制了浮点数的范围和精度，所以浮点运算只能近似地表示实数运算，因此采用一种系统的方法，找到最接近的匹配值 x'，可以用期望的浮点形式表示。

一个关键问题是：在两个可能值的中间确定舍入方向，一种可选的方法是维持实际数字的下界和上界，可以确定表示的值为 $x^{-} \, \, x^{+}$ ，使得 x 的值位于二者中间。浮点格式定义了四种不同的舍入方式，默认方法是找到最接近的匹配，而其他三种可用于计算上界与下界。

向偶数舍入（最接近的整数）：将数字向上或向下舍入，存在两个不同的值，则使得的结果为最低有效数字是偶数，因此，1.5与2.5的结果都舍入为 2。

向偶数舍入，当不想舍入到整数时，也可以向偶数舍入。只是简单地考虑最低有效位数字是奇数还是偶数。例：假设将十进制数舍入到最接近的百分位，1.2349999舍入到1.23，1.2350001舍入到1.24。而1.2350000和1.2450000都舍入到1.24（4是偶数）

向偶数舍入可以运用到二进制小数上，最低有效位的值0认为是偶数，值1是奇数，对形如X...X.Y....Y100...的二进制位模式的数舍入，XY为任意位值，最右边的Y是被舍入的位置，只有这种位模式表示在两个可能的结果中间的值。例如考虑舍入到最近的四分之一（二进制小数点后两位）的位置，10.00011舍入到10.00，10.00110舍入到10.01，因为它们不是两个可能值的正中间值。10.011100向上舍入成11.00（进一），10.10100舍入成10.10（退一），目的是将最后一位舍入为偶数（末尾为0）。

其他三种舍入方式：
零舍入：把正数向下舍入，把负数向上舍入；向上舍入：把正数和负数都向上舍入；向下舍入：把正数和负数都向下舍入。