1.数制与编码

1.1.进位计数法

1.1.1.进位计数法

进位计数法：进位计数法是一种计数的方法。常用的有十进制、二进制、八进制和十六进制等。日常生活中最常使用的就是十进制，其余则主要是计算机在运算是时使用。在进行计数法中，每个数所用到的不同数码的个数称为基数。

例如：十进制的基数为 0~9，每个数位计满 10 后就会向高位进位。

每个数码所表示的数值等于该数码本身乘以一个与它所在数位有关的常数，这个常数称为位权。一个进位数的数值大小就是它的各位数码按权相加。

例如：一个r进制数$(K_nK_{n-1}...K_0K_{-1}...K_{-m})$的数值可以表示为具${K_nr^2+K_{n-1}r^{n-1}+...+K_0r^0+K_{-1}r^{-1}+...+K_{-m}r^{-m}=\sum_{i=n}^{-m} k_ir^i}$，具体来说：

十进制：例如 975

$975.36 = 9 × 100 + 7 × 10 + 5 × 1 + 3 × 0.1 + 6 × 0.01 $ ，也即 $975 = 9 × 1 0 ^2 + 7 × 1 0 ^1 + 5 × 1 0^ 0 + 3 × 1 0 ^{− 1} + 6 × 1 0 ^{− 2} $
二进制：只有 0 和 1 两种数字符号，“逢 2 进 1”，其任意数位的权为$2^i$ ，i为所在位数。
八进制：八进制作为二进制的一种书写形式，其基数是 8，有 0~7 共 8 个不同的数字符号，“逢 8 进 1”。由于$ r=8=2^{3}$。
十六进制：其基数为 16，“逢 16 进 1”，其中 A、B、C、D、E、F 分别表示 10、11、12、13、14、15. 由于$r=16=2^{4}$。

1.1.2.计算机采用二进制编码的原因

原因如下：

二进制只有两种状态：使用有两个稳定状态的器件就可以表示二进制数的每一位，制造成本较低。比如可以利用高低电平和电荷正负表示 0 和 1。
二进制的 1 和 0 正好与逻辑值真和假相对应：这为计算机实现逻辑运算和程序中的逻辑判断提供了便利条件。
二进制的编码和运算规则很简单：通过逻辑门电路可以方便地实现算数运算。

1.2.进制转换

进制转换黄金原则（看完下面再看）：一切转换均可借助二进制作为媒介完成。

八进制、十六进制和二进制之间是有位数对应的关系的。
十进制和二进制可以直接通过权值累加得到。

1.2.2.其他进制数转换为十进制

其他进制数转换为十进制：其他进制数转化为十进制较为简单，只需代入下面的公式即可 ${K_nr^2+K_{n-1}r^{n-1}+...+K_0r^0+K_{-1}r^{-1}+...+K_{-m}r^{-m}=\sum_{i=n}^{-m} k_ir^i}$

例如：要把一个二进制数转为十进制数，那么上式中的 $r$ 就设为 2，然后用二进制数的每一位乘以 $ r^{n} $，这个 n 表示的是位权（小数点左侧从右向左由 0 递增，小数点右侧从左至右由 - 1 递减），再举几个例子：

二进制数 10010010.100 转化为十进制数： $10010010.110 = 1×2^{7}+1×2{4}+1×2^{1}+1×2{-1}+1×2^{-2}=146.75 $
**八进制数 251.5 转化为十进制数：$251.5 =2×8^{2}+5×8{1}+1×8^{0}+5×8{-1} $。
十六进制数 AE86.1 转化为十进制数： $AE86.1=10×16^{3}+14×16{2}+8×16^{1}+6×16{0}+1×16^{-1}=44678.0625 $

1.2.2.十进制数转化为其他进制数

十进制数转化为其他进制数：需要把整个过程分为求整数部分和求小数两部分。

求整数：第 i 次除以基数 b 所得到的的余数即为 $A_i$，然后继续利用所得商运算，直到所得商为 0，其中$i(1,n) $，最后结果反着写。
求小数：第 i次乘以基数 b 所得的整数部分即为$A_{-i}$，其中 $i\in (1,n)$，需要注意每次乘法之后要把个位处置 0。

例如：7562.03125 转化为 16 进制数。

首先，列一个表格计算整数部分：

整数部分为 1D8A。

除以 16	所得商	所得余数	对应符号
7562/16	472	10	A
472/16	29	8	8
29/16	1	13	D
1/16	0	1	1

然后计算小数部分：

注意：再进行下一次乘积运算时，要取上一次乘积的小数部分作为新的乘数进行运算，比如第二次运算乘积为 8，下一次运算时直接要取小数部分进行运算。
小数部分为 08。

乘以 16	所得乘积	取乘积整数位	对应符号
0.03125×16	0.5	0	0
0.5×16	8.0	8	8
0×16	0.0	0	0

到这里转换完成，答案为 1D8A.08。

上述方法是比较通用的方法。在实际情况中，尤其涉及编程、网络时，会频繁涉及到 10 进制数转化为 2 进制数的问题，所以这里还可以使用拼凑法，首先你需要牢记常用 $ 2^{n} $ 的值。

2 10 2^{10}	2 9 2^{9}	2 8 2^{8}	2 7 2^{7}	2 6 2^{6}	2 5 2^{5}	2 4 2^{4}	2 3 2^{3}	2 2 2^{2}	2 1 2^{1}	2 0 2^{0}	2 − 1 2^{-1}	2 − 2 2^{-2}	2 − 3 2^{-3}
1024	512	256	128	64	32	16	8	4	2	1	0.5	0.25	0.125

转换时，只需要目测估值即可，比如 260.75，260=256+4，同时 0.75 等于 0.5+0.25，相应位置填 1 即可。

2 10 2^{10}	2 9 2^{9}	2 8 2^{8}	2 7 2^{7}	2 6 2^{6}	2 5 2^{5}	2 4 2^{4}	2 3 2^{3}	2 2 2^{2}	2 1 2^{1}	2 0 2^{0}	2 − 1 2^{-1}	2 − 2 2^{-2}	2 − 3 2^{-3}
1024	512	256	128	64	32	16	8	4	2	1	0.5	0.25	0.125
0	0	1	0	0	0	0	0	1	0	0	1	1	0

所以 $(260.75){10}(100000100.11){2} $

1.2.3.二进制、八进制和十六进制的相互转换

二进制、八进制和十六进制的相互转换：这几个进制之间是具有对应关系的，所以可以快速转换。

八进制：八进制作为二进制的一种书写形式，其基数是 8，有 0~7 共 8 个不同的数字符号，“逢 8 进 1”。由于$ r=8=2^{3} $，所以 3 位二进制数码与 1 位八进制数码相对应。
十六进制：其基数为 16，“逢 16 进 1”，其中 A、B、C、D、E、F 分别表示 10、11、12、13、14、15. 由于 $r=16=2^{4}$，所以 4 位二进制数码与 1 位十六进制数码相对应。

因此转换时，以小数点作为起始点，向左向右分别进行划分，如果是八进制就是三位，如果是十六进制就是 4 位。

如果位数不足要把 “0” 补上，防止误判。

再比如：

$ (251.5){8}(010 101 001 . 101){2} $
$(AE86.1){16}(1010111010000110.0001 ){2} $

1.3.真值和机器数（考纲已删除）

真值：日常生活中，对于正数和负数我们可以使用正号 (通常省略) 和负号来表示，如 15 和 - 8。这种带 “+” 和“-”符号的数称为真值，真值是机器数所代表的实际值。

机器数：在计算机中，通常采用数的符号和数值一起编码的方法来表示数据。例如后面需要学习的原码，补码和反码。这几种表示法都将数据的符号数字化，通常用 “0” 表示正，用 “1” 表示负。

2.BCD码

2.1.什么是 BCD 码

BCD 码 (Binary-Coded Decimal)：是指二进制编码的十进制数。我们可以用 4 位二进制数来表示一位十进制数中的 0~9，这种编码方法使得二进制数和十进制数之间的转换得以快速进行。4 位二进制数最多有 16 种组合，足以表示 0 到 9 这十个数，所以有 6 种状态为冗余状态。

2.2.常用的 BCD 码

2.1.1.8421 码（最常用）

A：8421 码表示

8421 码 (Binary-Coded Decimal)：它是一种有权码，设其每一位的数值为$b1,b2,b3,b4 $，则权值从高到低依次为 8 , 4 , 2 , 1 ，它表示的十进制数为 $D=8b_{3}+4b_{2}+2b_{1}+1b_{0}$。

例如 985 的 8421 码为1001 1000 0101。

B：8421 码运算规则

8421 码运算规则：

如果两个 8421 码相加之和小于等于$(1001)_{2}$不需要修正。
**如果两个 8421 码相加之和大于$ (1001)_{2} $则需要修正：修正时需要 + 6**。

以 5+8 为例：

2.1.2.余 3 码

余 3 码：余 3 码是一种无权码，是在 8421 码的基础上加$(3)_{10}$，也即$ (0011)_{2}$形成的。

2.1.3.2421 码

2421 码：这是一种有权码。权值由高到低分别为 2 4 2 1，特点是大于等于 5 (5~9)的 4 位二进制数中最高位为 1，小于 5 (0~4)的最高位为 0。

3.无符号数的表示和运算

3.1.机器数的定点表示

根据小数点的位置是否固定，在计算机中有两类数据表示方法：定点表示和浮点表示。浮点表示类似于科学计数法，将在第三节介绍。

机器数的定点表示：定点表示就是约定机器数中的小数点位置固定不变，小数点不再使用.表示，而是约定其位置。理论上，小数点位置固定在任何一位都可以，但是在计算机中通常采用两种简单的约定：

定点整数：将小数点的位置固定在数据的最低位之后。
定点小数：将小数点的位置固定在数据的最高位之前。

3.2.无符号整数的概念及其在计算机中的应用

无符号整数（无符号数）：无符号整数是指整个机器字长的全部二进制位均为数值位，没有符号位，相当于数的绝对值，它就是我们常说的自然数； n 位无符号数其范围为$(0，2^{n}-1)$。

在 C 语言中，使用关键字unsigned修饰后，该变量即为无符号数。

unsigned int a = 1;
unsigned short b = 2;

以下讨论中假设机器字长为 8 位。

无符号整数硬件表示：由于无符号整数全部二进制位均为数值位，没有符号位，所以数值位均有位权，也即之前说到过的二进制。注意：

最小的无符号整数为全 0。
最大的无符号整数为全 1。
$n$位无符号数其范围为$(0,2^{n}-1)$，一旦超出则会溢出。

3.3.加法运算

无符号整数加法运算规则：从低位开始，按位相加，向更高位进位。

3.4.减法运算

无符号整数减法运算规则：由于减法电路实现较加法电路困难，所以成本较高，因此会将减法运算转换为加法运算来完成运算。具体来说：

被减数不变，减数按位取反、末位 + 1。
从低位开始，按位相加，向更高位进位。

注意高位被丢弃了。

4.有符号数的表示和运算

4.1.有符号数的概念及其在计算机中应用

有符号数：由于计算机是无法直接识别数的正负的，所以可以将符号数值化。规定：对于有符号数，用 "0" 表示正，用 "1" 表示负，且通常约定二进制数位的最高位为符号位。有符号数分为定点整数和定点小数。

定点整数和定点小数可以原码、反码、补码和移码(只有定点整数有)来表示。假设真值为x，则：

原码： $[x]_{原}$
反码： $[x]_{反}$
补码： $ [x]_{补} $
移码： [$[x]_{移}$

4.2.有符号数的表示

4.2.1.原码

原码：原码是一种比较简单、直观的机器数表示法。用机器数的最高位表示该数的符号，其余的各位表示数的绝对值，其中 0 表示正，1 表示负。

以 19.75 为例，假设机器字长为 8 位：

整数部分：19
小数部分：0.75

4.2.1.1.定点整数的原码表示

①：表示方法

定点整数的原码表示方法：按照二进制的位权书写即可，不足位可以用 0 补齐。

②：原码整数的表示范围

原码整数的表示范围：假如机器字长为n位，那么原码整数的表示范围为$ -(2^{n-1}-1) x ^{n-1}-1 $。

③：真值 0

真值 0 有 + 0 0 0 和 - 0 0 0两种形式。

4.2.1.2.定点小数的原码表示

①：表示方法

定点小数的原码表示方法：按照二进制的位权书写即可，不足位可以用 0 补齐。

②：原码小数的表示范围

原码小数数的表示范围：假如机器字长为 n 位，那么原码小数数的表示范围为$ -(1-2^{-n+1}) x -2^{-n+1} $。

③：真值 0

真值 0 有+ 0 0 0和- 0 0 0 两种形式。

4.2.2.反码

反码：反码是原码转换为补码的一个中间状态。

①：如果是正数，则反码与原码相同

例如 + 19D，其$ [x]{原}=0,0010011 [x] $， $ [x]{反}=0,0010011 $
例如 + 0.75D，其$[x]_{原}=0.1100000 $， $[x]_{反}=0.1100000$

②：如果是负数，则除符号位外，其他位按位取反

例如 - 19D，其$ [x]{原}=1,0010011$， $[x]{反}=1,1101100 [x] $
例如 - 0.75D，其 $ [x]{原}=1.1100000$， $[x]{反}=1.0011111 [x] $

③：特别注意真值 0 的 + 0 和 - 0 所对应的形式

[$ [+0]{原}=00000000 [+0] $，$[+0]{反}=00000000$
$ [-0]{原}=10000000$，$ [-0]{反}=11111111$

4.2.3.补码

①：如果是正数，则补码和原码一致

例如 + 19D，其 $ [x]{原}=0,0010011$， $ [x]{反}=0,0010011$， $[x]_{补}=0,0010011$
例如 + 0.75D，其$[x]{原}=0.1100000 [x] $， $[x]{反}=0.1100000 [x] $， $ [x]_{补}=0.1100000$

②：如果是负数，则补码 = 反码 + 1（注意进位）

例如 - 19D，其$ [x]{原}=1,0010011 $，$[x]{反}=1,1101100 [x] $， $ [x]_{补}=1,1101101 $
例如 - 0.75D，其 $ [x]{原}=1.1100000 $， $ [x]{反}=1.0011111 [x] $， $ [x]_{补}=1.0100000$

③：特别注意的是补码的真值 0 只有一种表现形式

因为 $ [-0]{原}=10000000 $， $ [-0]{反}=11111111 [−0] $，其补码如果在此基础再加 1，就会超出机器数位的限制（这里假定 8 位），变为$1,00000000 $。这样一来，低八位就又变成了 $00000000$，反而和 + 0 0 0冲突了，并且显得浪费，所以把我们这个特殊的补码直接规定为 $−128$。所以这里如果机器字长为 n 位，那么*补码整数的表示范围就为（多了一个-128）：

$ -(2^{n-1}) x ^{n-1}-1 $

相应的，补码小数 1.00000000 1.00000000 1.00000000 的表示范围会变为（多了一个 - 1）。 $-1 x -2^{-n+1} $

4.2.4.移码

移码只能用来表示整数，而不能表示小数。

移码：移码是在补码的基础上将符号位取反，需要注意移码只能用于表示整数，且移码和补码的真值 0 是保持一致的

例如 + 19D，其$ [x]{原}=0,0010011 $，$ [x]{反}=0,0010011 [x] $， $ [x]{补}=0,0010011 $， $ [x]{移}=1,0010011 $
例如 - 19D，其 $ [x]{原}=1,0010011 $， $ [x]{反}=1,1101100 [x] $， $ [x]{补}=1,1101101 $，$ [x]{移}=0,1101101 $

移码是补码的符号位取反，可以将其看做一个无符号数，因此真值增大时移码也在增大，可以很方便的使用移码对数的大小进行比较 。

4.3.原码、反码、补码总结

4.3.1.原码、补码运算技巧

如果已经知道 X 的补码，让你求 - X 的补码，只需所有位全部取反，末位 + 1 即可。
负数补码是在反码末位 + 1 后得到的，所以这就导致反码最右边连续的 1 都会因为进位而变为 0，直到进位碰到第一个 0 为止。因此，负数补码中，最右边的（最后一个 1）及其右面与原码相同，而其左面则与反码相同。

4.3.2.原码、反码、补码、移码特性（整数）

4.3.3.定点小数和定点整数对比

4.4.引入补码的目的

4.4.1.直接使用原码进行运算的弊端

对于无符号数，直接使用原码进行运算是没有问题的，如下图：

但对于有符号数，由于最高位表示的是符号位，所以下面计算的结果明显是错误的。

要想得到正确的运算结果，那就得要求计算机能够识别加减运算，也即算术逻辑单元 ALU 不只需要加法器，还得需要减法器才行。但由于减法器实现比较困难且成本巨大，所以一个可行的方案就是使用加法代替减法。

4.4.2.如何使用加法实现减法

如下是一个时钟，指针开始时指向的是 10，如果要让其指向 7，那么有两种方法：

逆时针旋转至 7：相当于做了减法，即10-3=7。
顺时针旋转至 7：相当于做了加法，但这里应该加多少呢？可以加 9，然后由于表盘最大数为 12，所以19%12=7，便指向了 7。

这个例子说明了一个道理：一个减法操作可以转换为一个与之对应的加法操作，而这里采用的是取余

-3 和 + 9 在 mod 12 这样的情况下是等价的，而这两个数相差正好就是 12。还有很多这样的数，比如 21、33、-15 等等，这些数之间的差距均为 12 或其倍数。

其实，上例中的 - 3 和 9 互为补数，因为这两个数的绝对值之和为 12。

$ -a(a>0) 的补数 = 模 -|a| $

补数的性质非常重要，假设互为补数的两数之和为 m，那么在 mod m 的条件下，若能找到负数的补数，就可以用正数的加法代替减法

如下例：

按照上面所述，要完成运算，只需要找到 - 14 的补数即可。这里机器字长为8bit，所以可以表示的数范围为$2^{8}− 1 $，这个$2^{8}− 1 $就相当于表盘上的 12，所以当某数大于 $2^{8}− 1 $ 时，由于机器字长的限制，计算机便帮助我们 “自动” 进行了一个 mod 运算，该数会被重新映射到合法范围内。

mod 12把数映射到了 0-11 这个范围内，mod $2^{8}$把数映射到了 $ 0-2^{8}-1 $这个范围内。

因此，-14 的补数为 $+ 1 , 00000000 - 00001110 = 11110010 $，大家认真观察就可以发现 -14 的补数其实就是 - 14 的补码。

最后，使用 11110010 11110010 11110010 替换原来的减法完成运算，其结果就是 0（截断）。

4.5.有符号数补码运算

原码运算不用多说，以下运算中必须把运算数全部转换为补码进行（特指负数）。

4.5.1.定点整数的补码运算

4.5.1.1.加法运算

定点整数补码加法运算规则：从最低位开始，按位相加（符号位参与运算），向更高位进位。

4.5.1.2.减法运算

定点整数补码减法运算规则：$ [A]{补} - [B]{补}= [A]{补} + [-B]{补}$，重点问题在于已知 $ [B]{补} $如何求$ [-B]{补}$，如下 ：

这样一来，减法就转变为了加法，剩余步骤同上。

4.5.2.定点小数的补码运算

4.5.2.1.加法运算

同定点整数运算规则

4.5.2.2.减法运算

同定点整数运算规则

4.6.溢出判别方法

如下，求 $ [A+C]{补} $和 $ [B-C]{补} $。运算过后你会得到一非常奇怪的结果。

这是因为发生了溢出，溢出分为上溢和下溢：

正数 + 正数导致上溢：正 + 正 = 负。
负数 + 负数导致下溢：负 + 负 = 正。

4.6.1.采用一位符号位依据溢出表达式判断

对于上面的例子：

$[A+C]_{补}=0,0001111+0,1111100=1,0001011$，真值 - 117
$ [B-C]_{补}=1,1101000+1,0000100=0,1101100$，真值 + 108

假设 A 的符号位为 $A_{s} $， B 的符号位为$ B_{S} $，其运算结果符号位为 $S_{s} $，则溢出逻辑表达式为：

$V=0 $表示无溢出。
$ V=1$ 表示有溢出。

$V=(A_{s}B_{s}(S_{s} ))+ ((A_{s})( B_{s})S_{s}) $

注意逻辑运算规则：

与： $A B C$表示与运算，A 与 B 与 C，当 A、B、C 全部为 1 时结果为 1，有一个为 0 结果为 0

或： $A+B+C $ 表示或运算，A 或 B 或 C，当 A、B、C 全部为 0 时结果为 0，有一个为 1 结果为 1

非： $A $ 表示非运算，比如 $A $为 1 则 $ A$ 为 0

在上面的例子中：

$ [A]{补}$符号位为 0， $ [C]{补} $符号位为 0， $ S_{s}= [ A + C]{补} $符号位为 1，则 $S{s} $为 0 ，因此$A_{s}C_{s}S_{s}$逻辑运算结果为 0；
$ {补} $为 **1**，$ {补} $为 **1**, 则$ (A_{s})( C_{s})S_{s}$结果为 1。

于是 $ V=000 + 111=0+1=1$（有溢出），其实这也对应了正数 + 正数必有溢出的结论。

负数 + 负数，也即 [ B − C ] 补 [B-C]_{补} [B−C] 补读者可以根据上面的逻辑自行验证，会发现也是溢出的。

逻辑表达式有了，接着就可以设计与之对应的电路结构，计算机在判断溢出时可根据此逻辑进行判断。

4.6.2.采用一位符号位依据数据位的进位情况判断

这里有两个进位需要区别开来：

符号位的进位$ C_{s}$：最高数值位向符号位进的位。
最高数值位的进位 $C_{1} $：最高数值位得到的进位。

溢出判断规则为：

上溢： $C_{s}=0 $， $ C_{1}=1$。
下溢：$ C_{s}=1 $， $C_{1}=0$。

比如$ [A+C]{补} $会上溢，所以运算时有$C{s}=0 $，$ C_{1}=1 $ 。

可以发现只要发生溢出$C_{s} 和 C_{1} $一定是不同的，计算机在判断时会使用异或运算。

$V = 0 $表示无溢出。
$V = 1 $ 表示有溢出。

$V=C_{s}⊕C_{1}$

4.6.3.采用双符号位判断（常考）

之前符号位都是一位，这种方法将符号位扩展为了 2 位。

“00” 表示正数
“11 表示负数”

如下为运算过程：

$[A+C]_{补}=00,0001111+00,1111100=01,0001011$，真值 - 117。
$ [B-C]_{补}=11,1101000+11,0000100=10,1101100 $，真值 + 108。

运算结果符号位自然也有两位，这两个符号位第一位表示本来应该的符号，第二位符号表示实际得到的符号。比如A+C 结果中本来正数 + 正数应该是正数，但是实际是负数，所以判断溢出，而且是上溢。

记这两个符号位为$S_{s1}S_{s2} $，则溢出表达式为：

$V = 0 $ 无溢出。
$V = 1$ 有溢出。

$ V=S_{s1}⊕S_{s2} $

4.7.符号扩展

从上面的叙述中可以看出，溢出现象发生的本质原因就是机器字长不够。所以最容易想到的一个方式就是把短数据扩展为长数据，比如int->long，那么这又带来一个新的问题就是：多出来的那些位应该如何填补？

对于定点正整数来说，由于其原码、反码和补码都一样，因此直接补0 即可。如 0,1011010 0,1011010 0,1011010—> 0,000000001011010 0,00000000 1011010 0,000000001011010。

对于定点负整数来说，原码补 0，反码则对应位置补 1，而补码根据前面讲到的规则从右向左数第一个 1 开始（包括）左侧部分同补码。

对于定点正小数，最后面补 0 即可。

对于定点负小数，和定点负整数同理。

5.字符与字符串在计算机中的表示详解（考纲删除了解即可）

现代计算机不仅要处理数值领域的问题，而且还要处理大量非数值领域的问题。这样一来，必然要引入文字、字母及某些专用符号，以便表示文字语言、逻辑语言等信息。例如，人机交换信息时使用英文字母、标点符号、十进制数及诸如$、%、+等符号。然而，数字计算机只能处理二进制数据，因此，上述信息应用到计算机中时，都必须编写成二进制格式的代码，也就是字符信息用数据表示，称为符号数据。

5.1.字符编码与 ASCII 编码

ASCII 编码：这是目前国际上普遍采用的一种字符系统，其美国版称为 ASCII 码 (美国国家信息交换标准字符码)。它包括 10 个十进制数码，26 个英文字母和一定数量的专用符号，如$、%、+等，总共 128 个元素。因此二进制编码需要 7 位，再加上一个校验位，共 8 位，刚好为一个字节。

ASCII 码字符排布情况如下：

0~31 为控制字符, 用于通信控制和设备的功能控制。
127 是 DEL 码。
32 是空格码。
32~196 共 95 个字符为可打印字符。
65~90 为大写字母范围。
97~122 位小写字母范围。
数字 0-9 的 ASCII 码为 48(011 0000) 到 57(011 1001)。注意去掉高三位后剩余部分正好是它们对应的 BCD 码形式。

5.2.汉字的表示和编码

汉字编码：在不同情况下需要使用到不同搞得汉字编码，主要有：

输入码：为了方便汉字输入而采取的编码方式。
内码：为了在计算机内部表示汉字而采取的编码方式。
输出码（字模码）：为了显示、打印汉字而采取的编码方式。

5.2.1.汉字的输入编码

汉字的输入编码：为了能直接使用西文标准键盘把汉字输入到计算机，就必须为汉字设计相应的输入编码方法，主要有以下三类：

数字编码（主要使用）：数字编码用数字串代表一个汉字输入。常用的是区位码，区位码是将国家标准局公布的 6763 个两级汉字分为 94 个区，每个区 94 位。也就说把汉字表示成二维数组，每个汉字在数组的下标就是区位码。区码和位码总共是两位十进制数字，所以输入一个汉字需要键入四次。例如下面的 “啊” 字位于第 16 区 01 位，所以它的区位码就是 1601。使用数字编码方式输入无重码，且与内码转换较为方便，但缺点即使代码太难记忆 。
拼音码：拼音码是以汉语拼音为基础的输入方法，只要掌握汉语拼音就可以轻松输入。但由于汉字同音字太多，所以输入的重码率会很高，输入速度也会受到影响。
字形编码：汉字总数虽然很多，但所有汉字都由最基本的笔画构成，因此全部汉字的部件和笔画是有限的。所以可以把汉字的笔画部件用字母或数字进行编码，按笔画的顺序依次输入就可以表示一个汉字。例如五笔打字。

5.2.2.汉字内码

5.2.2.1.国际码（交换码）

国际码（交换码）：上面说到的区位码还考虑一个问题，那就是必须要避开 ASCII 字符中 0~32 的不可显示字符和空格字符。因此会在区位码的基础上让其向后偏移 32，也就是加上 20H（十六进制），形成国际码。

注意：区码和位码必须同时加上 20H（因为区码和位码分别代表一个字节）。也即国际码 =(区位码)16+20H

5.2.2.2.汉字内码

国际码（交换码）：国标码还不能直接在计算机上使用，因为它还会和 ASCII 中的除控制字符外的其他字符冲突

这里以“中”字为例，其国标码中的高位字节为 86，这会与 ASCII 中大写字母’V’冲突，低位字节为 80，会与’P’冲突。

因此，为避免这种情况，规定：国标码中的每个字节的最高位都从 0 换成 1，相当于每个字节都再加上 128(十六进制为 80，即 80H；二进制为 1000 0000)，从而得到国标码的 “机内码” 表示，简称 “内码”。也即 汉字内码 =(国际码)16+ 80 H 80H 80H。

另外，由于 ASCII 码只用了一个字节的低 7 位，所以，一旦首位为 1 就表示这是汉字编码，若为 0 就是这是 ASCII 字符。

总之它们的关系如下：

5.2.2.3.汉字输出码（字模码）

汉字输出码（字模码）：为了显示或输出汉字，我们把汉字按图形符号设计成点阵图，就得到了相应的点阵代码 (字形码)。具体来说是用 0、1 表示汉字的字形，然后将汉字放入 $n$行 × $n$列的正方形 (点阵) 内，该正方形共有 n 2 n^{2} n2 个小方格，每个小方格用一位二进制表示，凡是笔划经过的方格值为 1，未经过的值为 0。

字节数 = 点阵行数 ×(点阵列数 / 8)。

同时，汉字信息处理系统还需要配有汉字字形库，也称字模库，简称字库，它集中了汉字的字形信息。当显示输出或打印输出时才检索字库，输出子模点阵，得到字形。

5.2.2.4总结

综上所述，这三类码关系如下：

5.3.字符串（考纲已删除）

字符串：字符串是指连续的一串字符。通常情况下，它们占用主存连续的多个字节，每个字节存一个字符。

英文字符，以 "abc" 为例。

计算机按字节编址，每个内存地址对应一个字节，最后一个字符往往是结束标志。

中文字符，以 "abc 啊" 为例。
两字节表示一个汉字。

6.校验码（考纲删除但计网会用建议学习）

6.1.基本概念

6.1.1.校验码

校验码：校验码是指能够发现或自动纠正错误的数据编码，也称检错纠错编码。具体实现时，校验码会增加一些冗余码，来帮助检验或纠错。

6.1.2.码字和码距

为了实现网络传输，会把原信息进行编码，形成二进制序列，这里就会涉及两个概念。

码字：由若干位代码组成的一个字称为码字，比如下图中 “00”，“01”。
码距：将两个码字逐位比较，具有不同的位的个数称为两个码字的距离，比如下图中 “00” 和“10”距离就是 1；一种编码方法可能有若干合法码字，各合法码字之间的最小距离称为 “码距”，下图所示编码方案其码距为 1。

码距大小与校验码的检错和纠错能力直接相关。

码距为 1 无检错能力。
码距大于等于 2 具有检错能力。
码距越大，检错、纠错能力就越强。
检错能力总大于等于纠错能力。

6.2.常见校验码

6.2.1.奇偶校验码

在原编码的基础上增加一个校验码，它的码距为 2，可以检测出一位错误 (或奇数位错误)，但不能确定出错位置，也不能检测出偶数位出错，增加的冗余位称为奇偶校验位。

实现方法：由若干位有效信息（比如 1B，0001 1011），再加上一个二进制位（检验位）组成校验码。如下图所示，校验位的取值为 0 或 1，它的加入使整个校验码中 “1” 的个数要么是奇数要么是偶数，所以就有两种可选的校验规律。

奇校验码：整个检验码中 “1” 的个数为奇数。
偶校验码：整个校验码中 “1” 的个数为偶数。

举个例子，1001101 的奇校验码和偶校验码设置如下：

奇偶校验具有很大的局限性，只能发现数据代码中的奇数位出错的情况 。

校验原理：传输前，发送端和接收端会协议确定彼此之间采用奇校验还是偶校验。以偶校验为例，计算机首先会将二进制所有位进行异或运算，所得结果就是偶校验位，比如上面信息 “1001101”，进行异或运算“1⊕0⊕0⊕1⊕1⊕0⊕1=0”，这表明 1 的个数为偶数个，故偶校验位为 0；接收端再接受信息后会进行异或运算，一旦结果出现 1 表明错误，比如上图中第一个例子，再接受到之后进行异或运算 “0⊕1⊕0⊕1⊕1⊕1⊕0⊕1=1”，所以结果错误（同时大家也可以发现如果再更改一位为 1，那么最终结果仍然是，这就是奇偶校验的局限性)。

6.2.海明校验码

海明码是一种广泛采用的有效的校验码，本质是一种多重奇偶校验码。其实现原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到奇偶校验组中。当某一位出现错误后，就会引起有关的几个校验位的值发生变化。它不但可以发现错误位置，还可以为自动纠错提供依据。

6.2.1.纠错理论

假设信息位为 n，校验位为k，因此 k 个比特位一共可以映射$2^{k} $ 种状态；海明码由信息位和校验位组成，因此共有 $n + k$ 位， $n+k$ 位每一个位置都有可能出现错误，因此这$2^{k} $种状态要把这$n+k $ 种全部映射到，但是要注意其中还要包含一种全部正确的情况。

综上所述，得出下面的重要不等式：

$2^{k}n+k+1 $

6.2.2.求解海明码

范例：求 1010 的海明码，具体流程如下：

6.2.2.1.确定海明码位数

此二进制序列信息位$n=4$，根据前述不等式： $2^{k}\geqslant n+k+1$，可知$ k $ 为 3 时不等式方可成立。

除了实际计算，也可以熟悉下面这张表，从而快速写出：

为了区分信息位和校验位，我们用$D_{4}D_{3}D_{2}D_{1} $表示信息位（对应$1010$）；用 $ P_{3}P_{2}P_{1} $表示校验位；整个海明码序列可以表示为 $ H_{7}H_{6}H_{5}H_{4}H_{3}H_{2}H_{1} $。

6.2.2.2.确定校验位分布

海明码中校验位不能直接放在信息位的头部和尾部。

规定：校验位 $p_{i}$应该放在海明码 $H_{2^{i-1}} $的位置，因此 $P_{1}P_{2}P_{3} $分别对应 $ H_{1}H_{2}H_{4}$，其实也就是 2 进制的权值。

校验位分布如下，首先放入校验位，信息位从低到高依次补全空位。

海明码位置	H7	H6	H5	H4	H3	H2	H1
分布情况	D4	D3	D2	P3	D1	P2	P1
海明码	1	0	1		0

接下来，由于校验位为 3 位，因此信息位需要根据校验位分为 3 组，每个分组分别进行偶校验。

6.2.2.3.求校验位的值

首先，我们需要海明码中对应位置为信息位的下标（也就是所处位置）转为二进制序列，比如上面表格中，$H_{7} $对应位置为信息，其下标为7，对应二进制序列为 111。

海明码位置	H7	H6	H5	H4	H3	H2	H1
分布情况	D4	D3	D2	P3	D1	P2	P1
信息位值	1	0	1		0

然后我们需要根据二进制序列确定每个校验位所在组包括哪些信息位。

前面我们说过， $P_{3}P_{2}P_{1} $实则对应的是二进制的权值421，而分组依据就是根据这个权值，比如 $P_{1} $表示所有二进制序列第 0 位为 1 的分到该组，所以 $ H_{3}H_{5}H_{7} $就分到了这一组。

分为三个组后，我们就要对每一组进行偶校验。上面内容提到，偶校验码计算实则通过异或运算完成，因此对每组进行异或运算，确定 P 的取值 。

填充表格如下：

海明码位置	H7	H6	H5	H4	H3	H2	H1
分布情况	D4	D3	D2	P3	D1	P2	P1
海明码	1	0	1	0	0	1	0

6.2.2.4.校验纠错

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查。这里是偶校验，如果$S_{3}S_{2}S_{1}$为 “000”，表明无错误。

如果 $ S_{3}S_{2}S_{1}$为 “010”，表明第 2 位出现错误。

其原理可以用下面的这张图解释。

比如$D_{3} $信息位发生变化，由于$D_{3} $包含于 $ P_{2} 和 P_{3} $，同时 $ P_{2} 和 P_{3}$又在 $ S_{2}S_{3}$的校验方程中，导致 $ S_{3}S_{2}S_{1} $为 `110 `，也就是$ H_{6} $发生改变。
再比如校验位 $ P_{2} $发生改变时，其只存在于$S_{2}$的校验方程中，所以 $ S_{3}S_{2}S_{1} $为 $ 010 $，也就是 $H_{2} $发生改变。

6.2.2.4.补充 - 全校验位

海明码具有 1 位的纠错能力和 2 位的检错能力

刚才设计的海明码，在使用时还是有一定问题的，比如发送刚数据为：

海明码位置	H7	H6	H5	H4	H3	H2	H1
分布情况	D4	D3	D2	P3	D1	P2	P1
海明码	1	0	1	0	0	1	0

发送中， $ P_{2}P_{1} $这两个校验位发生改变。

海明码位置	H7	H6	H5	H4	H3	H2	H1
分布情况	D4	D3	D2	P3	D1	P2	P1
海明码	1	0	1	0	0	0	1

那么按照之前的校验规则，$ S_{3}S_{2}S_{1} $的值为 “110”，表明$H_{3} $位置发生错误。很明显发现，判断错误，此时发生的是两个比特位的改变。所以之前的方案是没有办法区分 1 位错误，还是 2 位错误的。

为此，在使用时我们在海明码首部加入 “全校验位”，对整体统一进行一次偶校验。

发送方数据：

海明码位置	H8	H7	H6	H5	H4	H3	H2	H1
二进制		111	110	101		011
分布情况	P 全	D4	D3	D2	P3	D1	P2	P1
海明码	1	1	0	1	0	0	1	0

如果此时接收方校验后 $S_{3}S_{2}S_{1} $的值为 “000”，并且全体偶校验成功，表明没有错误；
如果$S_{3}S_{2}S_{1}$的值不为 “000”，并且全体偶校验失败，表明有 1 位错误，纠正即可；
如果 $S_{3}S_{2}S_{1} $的值不为 “000”，并且全体偶校验成功，很明显产生了两位错误，此时无法纠正，需要重传。

6.3.循环冗余校验码（CRC 码）

举个例子，A 要向 B 传送数据882，为了校验数据是否准确，A 和 B 约定了一个除数7，882除以7是可以出除尽的。在 B 接受到数据之后用，使用 882 除以 7，如果没有余数，表示数据可能正确，但如果有余数那么一定错误。

其实，CRC 的基本思想和刚才的除法思想基本一致。发送方和接收方提前约定好一个数，作为除数（这里的数自然指的是二进制序列），在 K个信息位后拼接 R个校验位作为被除数（添加校验位需要保证除法余数为 0），接受方在接收到数据之后进行相应除法运算，检查余数是否为 0。

一般来说题目会将除数表现一种多项式的形式，比如：设多项式 $ G(x)=x^{3}+x{2}+1 $，信息码为 $101001$，求对应的$ C R C$ 码。

多项式 $G (x) $的完整形式实则为 $G(x)=1x^{3}+1x{2}+0x^{1}+1x{0} $，取系数，指明除数为 $1101 $。

1：确定K、 R以及生成多项式对应的二进制码

其中 $R= 生成多项式最高幂次 = 3 $， $K= 信息码长度的 = 6 $，于是整个编码位数$N=K+R=9 $ 多项式$ G (x) $对应二进制码为$ 1101 $

2：移位

现在我们要确保添加的 3 位校验位形成的被除数可以整除除数，因此首先将信息码 101001左移 R 位，低位补 0，也即 101001000，称其为新信息码。

3：相除
对于新信息码，用生成多项式进行模 2 除法，产生余数。

举个例子，用 1001000 作为被除数，1011 作为除数，模 2 除法为的是求余数，不关心商。

首先商为 1，得出结果。

此时不应该做减法，而应该做对应为的异或运算。

接着如果高位为 0，就抹去一位，同时后面用被除数的补齐一位。

这里经过异或运算，然后抹位补位得到的结果（比如上图 0100）中，如果首位为 0 就商 0，首位为 1 就商 1 。

继续异或，然后抹位，补位后。

继续。

运算到这里，其实可以进行快捷操作。异或后前面有多少 0 都全部扔掉，再从被除数哪里补齐相应位即可。但是这里很明显只能取一个，于是就得到下面的结果，此时也是最终结果，因为余数位数小于除数 。

好的，回到正题。此时运算出的余数为 001，作为校验位。于是整个 CRC 码即为$信息码 + 校验码 = 101001001 $。

4：检验纠错

接收方接受到到数据后，使用约定的除数进行模 2 除运算，如果余数为 000，结果正确。如果接收方数据为101001011（导数第二位出现错误），计算结果为 010，对应是十进制数为 2，表示第二位出现错误，但是特别注意这只是巧合，出错位置与计算结果没有必然联系，但是也有一定联系。

我们把每一个位置出错的情况统计如下，大家可以发现，余数为 3 位最多映射 8 种情况，因此第 1-7 位是属于一个周期，但是从第 8 位又开始了一个新的周期，因此 010 有可能对应第 2 位出错，也有可能是第 9 位。

难道说 CRC 码不能确定出错位置吗？其实也不是的，出现这种情况的原因主要在于信息位过长，无法一一映射。所以要想确定纠错位置就要选择合适的多项式 (纠错 1 位)，具体关系如下面不等式：

$ 2^{R}K+R+1$

其实这和海明码类似。但是实际应用中，尤其在网络中主要用来检错。

7.算数逻辑单元和电路基本知识以及基本逻辑运算和全加器

7.1.算数逻辑单元 ALU

数字运算过程中一直离不开一个十分重要的部件——运算器，其构成如下：

其中有一个核心部件——算数逻辑单元 ( Arithmetic and Logic Unit )，也即 ALU，其作用主要有以下三类

算数运算：如加、减、乘、除等。
逻辑运算：如与、或、非、异或等。
辅助功能：如移位、求补等。

大家在课本中见到的 ALU 经常会被画成这样：

$A_{i}B_{i} $：是输入信号，这是一种电信号。通过高低电平，输入不同的电信号。
$F_{i} $：这是输出信号，也就是运算结果。
$K_{i} $：这是控制信号，由控制单元发出 (CU)；控制单元负责解析指令，比如这个运算是什么类型的运算等等。

上面是抽象图，下面是一个比较具体的图象，经典的 74181 芯片，是一个 4 位的 ALU 。

上面的 M 会指明当前是一个逻辑运算还是算数运算（M=1 是逻辑运算，M=0 是算数运算)。总之，ALU 是在输入输出和控制信号下工作的。

7.2.最基本的逻辑运算

7.2.1.与、或、非

无论是多复杂的逻辑还是算数运算，都是通过最基本的逻辑运算复合而成的，这里最基本的逻辑运算指的是一个位的运算，他们分别是 “与”、“或” 和非。

与：全 1 才是 1，有 0 就是 0。
或：全 0 才是 0，有 1 就是 1。
非：0 为，1 为 0。

上面是从数学抽象的角度来描述的，它们对应的真实电路是如下三个门电路（从左到右依次为：与、或和非）：

与：只有 A 和 B 全部输入为高电平时，Y 才会是高电平，只要有一个是低电平 Y 就会是低电平。
或：如果 A 和 B 输入中有一个是高电平时，Y 就会是高电平，只有全部输入为低电平时，输出才会是低电平。
非：输入的是高输出的就是低，反之亦然 。

另外需要注意这几个运算的表达式：

与： $ Y=A▪B$
或： $ Y=A+B$
非： $=A+{B} $

其中与的优先级要大于或，也就是对于 $ AB+CD $，要先计算与再计算或，他们也满足一些计算定律：

分配律： $ A(C+D)=AC+AD $
结合律： $ABC=A(BC) $、$A+B+C=A+(B+C) $

在掌握与、或、非这三种基本运算后，我们就可以实现任何一种复杂的逻辑运算了。

例如：实现 $ AC+AD$

这是一个逻辑运算，可以让 A 和 C 以及 A 和 D 分别进行与运算然后结果再进行或运算。

也可以转变为等价的运算，即$A(C+D) $，先让 C 和 D 进行或运算，然后再和 A 进行与运算，这样一来还节省了一个电路元件。

7.2.2.与非、或非、异或、同或

与非：实则是与运算取反；也就是说全 1 则为 0，全 0 则为 1，有 1 则是 1。
或非：实则是或运算取反；也就是说全 1 则为 0，全 0 则为 1，有 0 则是 0。
异或：相同数异或运算结果为 0,0 异或任何数是任何数。
同或：相同数异或运算结果为 1,1 异或任何数是任何数。

他们对应的电路符号分别为：

7.3.一位全加器

一位全加器：一位全加器（FA）是最基本的加法单元，首先注意以下两个概念。

本位：指的是当前运算的那一位。
本位的和：包括本位对应的两个数和来自低位向本位的进位。

运算时是按照一位一位的方式加的，来自本位的两个数和来自低位的进位会确定本位的和，同时确定向高位进位的数值。

因此输入共有三个：

$A_{i} $和 $B_{i} $以及$ C_{i-1}$

输出共有两个：

**第一个是$ S_{i} $**：由于是二进制，因此$ S_{i} $只能是 1 或者是 0，所以就可以使用异或运算确定输入中 1 的奇偶个数，如果有奇数个 1 那么结果为 1，否则为 0，也即$ S_{i}=A_{i}⊕B_{i}⊕C_{i-1}$。
第二个是 $C_{i} $：第一种情况就是 $ A_{i}=1 且 B_{i}=1 $，那么无论进位为多少都要进一位；**第二种情况**就是$A_{i} 和 B_{i}$中有一个本位为 1 并且来自低位的进位是 1。这两种情况属于或的关系，因此逻辑表达式为：$ C_{i}=A_{i}B_{i}+(A_{i}⊕B_{i})C_{i-1}$

因此电路表示可以为 ：

屏蔽内部实现细节后：

7.4.串行加法器和并行加法器

7.4.1.串行加法器

串行加法器：串行加法器中只有一个全加器，数据会逐位串行送入加法器中进行运算。进位触发器用来寄存进位信号，以便参与下一次运算。

缺点：如果操作数为 n位，加法就要分 n次进行，每次产生一位和并且串行逐位送回寄存器中，所以效率非常低。

7.4.2.并行加法器（串行进位）

串行进位的并行加法器：最简单的并行加法器是串行进位的并行加法器：是将多个加法器串联在一起，这样就能同时输入两个 $n$位的数，每一位都可以使用一个加法器进行就算，且低位加法器产生的进位，会作为下一个高位加法器的输入信号。

缺陷：电信号的传递时需要时间的，因此高位的操作会受到低位的限制。

7.4.3.并行加法器（并行进位）

并行加法器（并行进位）：与串行进位的并行加法器相比，并行进位的并行加法器的各级进位信号同时生成，即同时进位。

如下，记 $G_{i}=A_{i}B_{i} $， $P_{i}=A_{i}⊕B_{i} $，则由

$ C_{i}=A_{i}B_{i}+(A_{i}⊕B_{i})C_{i-1}=G_{i}+P_{i}C_{i-1} $

所以 $G_{i} $和 $P_{i}$会被同时送入加法器，大大提高了效率。

8.补码加减运算器和标志位的生成

8.1.补码加减运算器

8.1.1.补码加 / 减法运算规则回顾（即手算方法）

n bit 补码 $X$+ $Y$：直接按位相加即可。
n bit 补码 $X$- $Y$：将$ [Y]{补} $全部按位取反，末位 + 1**，得到$ [-Y]{补} $，使减法变为加法**。

例如：$X=-8 $， $Y=7 $，即 $ [X]{补}=1000 $， $ [Y]{补}=0111$，则

$X+Y=1111$
$ X-Y=1000+(1000+1)=0001$（溢出）

例如： $X=3 $，$Y=4 $，即$ [X]{补}=0011$，$ [Y]{补}=0100$，则

$X+Y=0111 $
$X-Y=0011+(1011+1)=1111$（溢出）

8.2.补码加减运算器原理

8.2.1.普通加法器回顾

下图是前面讲过的普通加法器原理图，并没有实现补码加减功能，其中：

$ A$ 和 $B$：这是两个 n bit 的操作数，它们需要按位相加。
$Cin$：这是来自低位的进位，该进位需要加在 $ A$ 和 $B$ 的最低位。
$F$：这是运算后产生的结果。
$Cout $：这是运算后产生的进位，该进位由 $ A$ 和 $B$ 的最高位运算后给出。

8.2.2.补码加减运算器

如下是补码加减运算器，其中红色线上方和普通的加法器是一样的，下方是为实现补码运算所增加的电路。在进行补码运算时，对加减运算的区分会由信号 Sub 给出（0 为加，1 为减），该信号会传送给多路选择器 MUX，让其接通加法或减法电路。

8.2.2.1.加法功能

实现加法功能时，Sub 为 0，多路选择器直接连接 $Y$ 的一端会被选通，让 cin 为 0，然后进行运算即可。

8.2.2.2.减法功能

实现减法功能时，Sub 为 1， $Y$ 会进入带有非门的一端，经过非门后 $Y$ 会被取反，然后让 cin 为 1，相当于取反后再 + 1，接着完成运算即可。

8.3.标志位的生成

加法器在产生运算结果 $F$ 的同时，还会产生如下 4 个标志位，用于辅助后续运算判断：

$OF $（Overflow Flag 溢出标志）：溢出为 1，否则为 0，对于无符号数运算，OF没有意义。
$ SF $（sign Flag 符号标志）：结果是负为 1，否则为 0，对于无符号数运算，SF没有意义。
$ ZF $（Zero Flag 零标志）：运算结果是 0 位 1，否则为 0，无符号数和带符号数运算，ZF都有意义。
$ CF $（Carry Flag进位 / 借位标志）：进位 / 借位时为 1，否则为 0，判断是否发生溢出。

8.3.1.OF 硬件产生方法

OF 硬件产生方法：$最高位产生的进位 C_{s} ⊕ 次高位产生的进位C_{1} $ 。

例如：$ [A+C]{补}=0,0001111+0,1111100=1,0001011 $，真值 - 117。由于 $C{s}=0 $， $ C_{1}=1 $，所以溢出。

8.3.2.SF 硬件产生方法

SF 硬件产生方法：它等于最高位的本位和，注意 SF 对无符号数加减无意义。

8.3.3. ZF 硬件产生方法

ZF 硬件产生方法：只有当运算结果所有比特位全为 0 时，ZF 才等于 1。

8.3.4. CF 硬件产生方法

CF 硬件产生方法：$最高位产生的进位 C_{s} ⊕ sub $信号，注意 CF 对有符号数的加减法无意义。

8.4.5.总结

9.定点数的移位运算

定点数的移位运算：根据操作对象的不同可以划分为

算数移位： 有符号数的移位。
逻辑移位： 操作对象是逻辑代码，可视为无符号数。

其实我们很早之前就已经接触过移位运算了。

比如 $ 985.211 × 10^{1} =9852.11 $就相当于小数点右移 1 位。
比如 $985.211 ^{1}=98.5211 $ 就相当于小数点左移 1位。

移位的本质：通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权。

9.1.算数移位

算数移位： 算数移位的对象是有符号数，在移位的过程中符号位保持不变。

9.1.1.原码的算数移位

算数右移：

如果移出去的是 0，那么算数右移相当于除以了 2。
如果移出去的是 1，会丢失精度。

如下是 - 20 的原码：

算数右移时：符号位不动，向右移动 1 位，高位补 0。

由于移出去的是 0，所以 - 20 变为了 - 10,-10 变为了 - 5 。

此时最低位为 1，再次右移一位，其结果为 - 2。

移出去的是 1，精度丢失。

算数左移：

如果移出去的是 0，那么算数左移相当于乘以了 2。
如果移出去的是非 0，会丢失精度。

算数左移时：符号位不动，低位补 0。

由于移出去的是 0，所以 - 20 变为了 - 40，-40 变为了 - 80 。

此时最高位为 1，再次左移一位，出现严重误差。

左移时，要将高位的 1 抛弃，而 7 位二进制表示范围为 - 128~128，理想的结果 - 160，自然超出了范围。

9.1.2.反码的算术移位

正数的反码算数移位和原码相同。

负数的反码算数移位：反码除了符号位外其余各位和原码是一一取反的，因此反码的 1 对应原码的 0，反码的 0 对应原码的 1。所以反码算数右移时高位补 1，低位舍弃；算数左移时低位补 1，高位舍弃。

9.1.3.补码的算数移位

正数的补码算数移位和原码相同。

负数的补码算数移位：负数补码是在反码末位 + 1 后得到的，所以这就导致反码最右边连续的 1 都会因为进位而变为 0，直到进位碰到第一个 0 为止。因此，负数补码中，最右边的（最后一个 1）及其右面与原码相同，而其左面则与反码相同。

因此，补码算数右移时和反码相同，也即高位补 1，低位舍弃；而算数左移时又会和原码相同，也就是低位补 0，高位舍弃 。

9.1.4.总结

9.2.逻辑移位

逻辑移位： 逻辑移位比较简单，可以看作是对 “无符号数” 的算数移位。

逻辑右移时高位补 0，低位舍弃。
逻辑左移时低位补 0，高位舍弃 。

9.3.循环移位

循环移位：循环移位分为如下两种

带进位标志位 CF 的循环移位（大循环）。
不带进行标志位的循环移位（小循环）。

循环移位的特点是：移出的数位又被移入数据中，是否需要进位则看有没有将进位标志加入循环位移。循环位移十分适合将数据的低字节和高字节之间进行互换。

10.定点数乘法运算（原码/补码一位乘法）

10.1.乘法运算基本思想

关定点数的乘法，其实我们在小学就学习过，就是经典列竖式相乘：

其中，我们印象最深的应该就是计算过程中的错位问题了。

在计算机中，相乘时使用的二进制，其基本逻辑和竖式相乘一致。如下是两个二进制数相乘，其中被乘数为0.1101，乘数为 0.1011 。

我们将乘数看作为位权之和，即$ 0.1011=1×2^{-1}+0×2{-2}+1×2^{-3}+1×2{-4} $。，被乘数写成 $ A$ 与$ 2^{n} $相乘的形式，即 $ 0.1101=1101×2^{-4}$。

那么此乘法过程可以等价为下面的形式：

把竖式写全也就是下面的这个样子：

由于二进制的乘数每一位只可能出现 0 或 1，因此每次运算的结果要么是全 0，要么只是被乘数乘以 $2^{n}$，实际结果只是小数点的不同，而计算机处理小数点位置非常方面，使用移位操作即可完成。

10.2.原码一位乘法

10.2.1.实现原理

逻辑看似很简单，但是如何让机器实现这是一个问题。如果要实现这一问题，必须解决以下三个问题：

实际数字有正有负，符号位应当如何处理？
乘积运算时位数扩大很厉害，如何处理？
每次运算时的结果都要保存下来，如果相加？

其中符号位很方便处理，符号位 = $s =x_{s}⊕y_{s} $即可判断，让数值位取绝对值进行乘法运算即可。

case：机器字长为 $n+1=5$位， $ [x]{原}=0.1101，[y]{原}=0.1011 $，采用原码一位乘法求 $xy $。

还记得 (计算机组成原理) 第一章计算机系统概述 -计算机硬件组成 (存储器、运算器和控制器概述及计算机工作过程详解) 这一节我们讲到过的运算器的组成吗？其中涉及乘法时会用到 $ACC $， $MQ $， $X$ 这三个寄存器。

接下来我们详细叙述一下这个过程。开始， $X$ 是被乘数， $Y$ 是乘数，因此 $X$ 位于 X 寄存器中， $Y$ 位于 MQ 寄存器中，并且运算开始前要将 ACC 置为 0 。

对应我们竖式乘法的逻辑，此时从低位到高位，依次用乘数的每一位乘被乘数，因此在这里进行第一次运算时我们把 MQ 寄存器中参与运算的那一位方块的颜色加深。

如果当前参与运算的乘数的这一位是 1，则 $ACC $ 加上被乘数；如果当前位是 0，则 $ACC $ 加上 0，也即(ACC)+(X)->(ACC) 。

在进行下一位竖式运算时，必须偏移一个位置，对应于计算机处理时则是让 ACC 和 MQ 中的数据统一逻辑右移一位 。

这样做本质实现的就是错位相加。

接着次低位来到了最低位的位置，再次进行(ACC)+(X)->(ACC) 。

剩余的步骤均重复上述过程。

10.2.2.手算模拟

考试的时候，如果出到这样的题目，具体步骤如下 ：

设 $s [X]_{原}=x_{s}$，$ s [Y]{原}=y{s}$

被乘数和乘数均取绝对值参与运算，符号位为 $ x_{s}⊕y_{s}$。
部分积的长度同被乘数，取 $n+1 $位，以便存放乘法过程中绝对值大于等于的值，初值为0。
从乘数的最低位 $y_{n}$开始判断：若$y_{n}=1$，则部分积加上被乘数 $|x| $，然后右移一位；若 $y_{n}=0 $，则部分积加上 0，然后右移一位。
重复步骤 3，判断 $n$次。

注意：

由于乘积的数值部分是两数绝对值相乘的结果，因此原码一位乘法运算过程中的右移均为逻辑右移。
考虑到运算时可能出现绝对值大于 1 的情况（但并非溢出），所以部分积和被乘数取双符号。

case: 设机器字长为 5 位（n+1）, $ x=-0.1101$，$ y=0.1011$，采用原码一位乘法求解 $xy $。

解： $|x|=00.1101 $, $ |y|=00.1011$，过程如下：

因此符号位为 $ P_{s}=x_{s}⊕y_{s}=1=1⊕0=1 $，得 $ x·y=-0.10001111 $。

11.补码一位乘法（ Booth算法，考察重点）

定点数乘法中最有可能考察的便是补码一位乘法。因为机器做加减法时采用的是补码，倘若做乘法前再将补码转为原码，计算完成之后再转化为补码，那就很麻烦了，还不如直接用补码计算。

补码一位乘法主要分为校正法和比较法，校正法了解即可，而比较法（又叫Booth算法）则是考察的重点。具体规则如下：

①：被乘数与部分积一般取双符号位，并且符号位参与运算。

一个原因是一旦符号位参与运算就一定要使用多符号位，因为一旦溢出，单符号位就会出错
另一个原因是，补码的右移时要看符号位而定的，如果采用单符号位，一旦数值部分的进位把符号给移掉了，下次移位就不知道该怎么办了。

②：乘数取单符号位以决定最后一步是否需要校正，也即是否需要加$[-x]_{补}$
③：乘数末尾增设辅助位，$y_{n+1} $，初始值为 0** ④：**根据 ($y_{n} $，$ y_{n+1} $)判断位，进行运算，步骤和上面原码一位乘法一致
⑤：按上述算法进行 n+1, 其中最后一步也即 n+1 步不再移位，仅根据 $ y_{0},y_{1} $比较结果决定是否需要加减 $ x_[补] $

从上面图中大家可以看出 MQ 中的最低位现在是辅助位，这里就和原码乘法的最低位不一致了，所以这里我们用带有双引号的——“最低位” 表示运算时真正的最低位，而不是辅助位

辅助位减 “最低位”=1 时，$ (ACC)+[x]_{补}$
辅助位减 “最低位”=0 时，$ (ACC)+0$
辅助位减 “最低位”=-1 时， $ (ACC)+[-x]_{补}$

$case $: 假设机器字长为 5 位（含 1 位符号位，$n=4 $）， $x=-0.1101$，$y=0.1011$，采用 $Booth$ 算法求 $xy $。

解：$[x]_{补}=11.0011$，$ [-x]{补}=00.1101$，$ [y]{补}=0.1011 $。

12.定点数除法运算（原码/补码一位除法）

12.1.除法运算基本思想

关于定点数的除法，我们在小学其实就已经学习过了，就是列竖式除法, 比如 $0.211÷0.985 $，我们首先习惯同时扩大 $n$倍。

在上面的例子中， $ 0.211÷0.985=0.214 $ 余 210，它就等价于 $0.211=0.985×0.214+0.000210 $，也就是说这可以转为成乘法的，也即：

在计算机中，运算时使用的是二进制，比如$ x=0.1011$（被除数），$y=0.1101$（除数)， $ x÷y $ 如下：

运算时忽略小数点，每确定一位商就进行一次减法，得到 4 位余数，在余数末尾补 0，再确定下一位商，确定 5 位商即可停止（这里机器字长是 5 位）。

如果补位后所得余数部分大于除数，那么就商 1。
如果补位后所得余数部分小于余数，那么就商 0。

和乘法一样，补全位数后就是下面这样：

因此 $x÷y$ 结果为 0.1101，余数为 $0.00000111$。

12.2.原码一位除法(恢复余数法)

12.2.1.实现原理

逻辑看似很简单，但是如何让机器实现这是一个问题。其中符号位的处理就不用再强调了，和乘法一样，仍然使用异或完成，于是实际运算时采用两个数的绝对值完成。

$case: $设机器字长为 5 位（$ n=4$，一位符号位）， $ x=0.1011$， $ y=0.1101$，采用恢复余数法求 $x÷y$

$∣x∣=0.1011$
$ |y|=0.1101$
$ [|y|]_{补}=0.1101$
$[-|y|]_{补}=1.0011 $

还记得 (计算机组成原理) 第一章计算机系统概述 - 计算机硬件组成 (存储器、运算器和控制器概述及计算机工作过程详解) 这一节我们讲到过的运算器的组成吗，其中涉及除法时会用到 $ACC $， $MQ $， $X$ 这三个寄存器。

开始的时候， $Y$ 是除数，位于 X 寄存器内，ACC 寄存器存放的是被除数（x）或余数，MQ 中存放商，MQ 中灰色加重的方格表示当前要确定的一位商 。

前面手算时，每一位商到底取 0 还是 1，是通过判断当前余数和除数的大小确定的，因此很显然，我们的 ACC 寄存区和 X 寄存区天然就存储了余数和除数。但实际情况是，计算机并不会进行比较，它会不管三七二十一直接商 1，如果出错再改为商 0，并恢复余数。

商 1 时，其实就是余数减去除数, 也即是(ACC)-(X)->ACC。

于是，这里首先计算机先商 1（但是本应该先商 0），因此此时就会求余数：(ACC)-(X)->ACC, 也即$[-|y|]_{补} $（计算机依靠加法实现减法），也即$ 01011+10011=11110 $。

此时符号位 1，计算机察觉错误，于是改为商 0，同时既然是商 0，那么就不应该减去除数，而应该减去 0（什么也不做），所以这里直接采取逆过程，加上除数即可。

所以现在我们就完成了一位的商，在手算中，我们商完一位后会错位一位补位，然后再商下一位，而在这里对应的就是将 ACC 和 MQ 中的内容逻辑左移即可。

接着计算机再次商 1，此时检查符号位为 0，说明是正的，说明计算机没有商错误，那么不需要恢复余数。

剩下的就是不断左移，运算的过程了。

最后我们假定的机器字长为 5 位，因此只能求 5 位的商。不过需要注意的是，如果最后一位商 1 后，导致了 ACC 出现负数，那么仍然需要改为 0，并恢复余数 。

最后，我们这里举的例子是小数，所以其小数点的位置隐含在符号位后面。最后实际的余数是 $2^{-n} $（ $n$为机器字长） 。

12.2.2.手算模拟

考试的时候，如果出到这样的题目，具体步骤如下 。 $case: $设机器字长为 5 位（$ n=4$，一位符号位）， $ x=0.1011$， $ y=0.1101$，采用恢复余数法求 $x÷y$

$∣x∣=0.1011$
$ |y|=0.1101$
$ [|y|]_{补}=0.1101$
$[-|y|]_{补}=1.0011 $

12.3.原码一位除法：加减交替法（不恢复余数法）

可以看出恢复余数法实际还是挺繁琐的，主要是当余数为负时，它还要加上除数，恢复到上一状态再左移。

而加减交替法是恢复余数的优化，具体规则为：若余数为负，直接商 0，并让余数左移 1 位再加上除数

$case$ : 设机器字长为 5 位（$ n=4$，一位符号位）， $ x=0.1011$， $ y=0.1101$，采用恢复余数法求 $X$÷ $Y$

$∣x∣=0.1011$
$ |y|=0.1101$
$ [|y|]_{补}=0.1101$
$[-|y|]_{补}=1.0011 $

注意：最后一步如果出现负数，仍然需要恢复余数！！！

12.4.补码一位除法

补码除法采用加减交替法完成，与原码除法的有所区别的是：

符号位参与运算。
被除数（余数）、除数采用双符号位。

运算的具体细节区别如下：

原码除法，首先一上来就会让被除数减去除数的绝对值的补码；在补码除法中，若被除数和除数同号，则被除数减去除数，如果异号，则被除数加上除数。
得到新的余数后判断：若余数和除数同号，则商 1，余数左移一位减去除数；若余数和除数异号，则商 0，余数左移一位加上除数。
在原码除法中如果最后一步余数出现负值，那么需要进行恢复余数；在补码除法中，我们直接把最后一位商置为 1 即可，这样做很省事，其精度也不会超过 $2^{-n} $。

$case: $设机器字长为 5 位（$ n=4$，一位符号位），$+x=0.1000 $， $y=-0.1011 $，采用补码加减交替法求 $x÷y$

$ [x]_{补}=00.1000 $
$ [y]_{补}=11.0101 $
$ [-y]_{补}=00.1011 $

因此最后的结果$[x/y]_{补}=1.0101$，余数为 $0.0111×2^{-4} $。

12.5.总结

13.详解C语言中的强制类型转换

13.1.无符号数和有符号数

有如下代码：

int main()
{
	short x=-4321;//短整型，顶点负整数
	unsigned short y = (unsigned short)x;//无符号短整型
}

我们知道在计算机中数据是以补码的形式保存的，因此变量x的补码形式为：

1110 1111 0001 1111

第二句代码进行强制类型转换，把一个有符号转换为了无符号，并用无符号变量保存；在这个过程中数据的内容是没有被改变的，只是改变了解释的方式，也就说说变量 y 的内容依然是：

1110 1111 0001 1111

但是在解释是计算机会把第一位的符号位当作数值位，因此 y 对应的真值是 61215。

13.2.长整数变为短整数

有如下代码：

int a=165537,b=-34991;//整形
short c=(short)a;
short d=(short)b;//强制类型转换，长整形转为短整型

这个例子中短整型为 16 位，整形为 32 位，因此将长整形转换为短整型，短整型的变量肯定不能完全保存，会丢失精度。具体规则为：高位截断，保留低位。

比如 a 的十六进制为：

0x000286a1
0010 1000 0110 1010 0001//二进制形式

使用 c 保存后，值为：

0x86a1
1000 0110 1010 0001//二进制形式

1000 0110 1010 0001是 c 的补码，属于有符号数，是一个负数，其原码（负数原码等于补码除符号位按位取反后 + 1）为1111 1001 0101 1111，对应真值 - 31071。

再比如，b 的十六进制为：

0xffff7751
1111 1111 1111 1111 0111 0111 0101 0001//二进制形式

使用 d 保存后，值为：

0x7751
0111 0111 0101 0001//二进制形式

0111 0111 0101 0001是 d 的补码，属于有符号数，是一个正数，其原码（正数原码和补码一致）为0111 0111 0101 0001，对应真值 30545。

13.3.短整数变为长整数

有如下代码：

short x=-4321;//短整型
int m=x;//使用整形保存短整型
unsigned short n=(unsigned short)x;//将x强制转为为无符号，然后复制给无符号短整型
unsigned int p = n;//把无符号短整型n变为无符号整形

这属于之前讲到过的符号扩展问题。这里 x 是一个负数，所以会在符号位和原有的数值位之间添上 1，这样做最后的结果不改变，只是补码的长度发生改变。

unsigned short n=(unsigned short)x将 x 这个有符号短整型转换为了无符号短整型，计算机会将其补码原封不动的赋值给 n，但是会按照无符号的规则解析真值，真值为 61215。

unsigned int p = n属于无符号到无符号的转换，直接填 0 即可。

14.数据的存储和排列

14.1.大小端模式

在存储数据的时候，数据从低位到高位可以从左到右排列，也可以按从右到左的方式排列。因此，我们无法用最左或最右来表征数据的最高位或最低位，通常用最低有效字节（$LSB $）和最高有效字节 ( $ MSB $) 来分别表示数的低位和高位

现代计算机基本采用字节编址，即每个地址编号存放一个字节。不同类型的数据占用的字节数不同，（int 和 float 的数据占用 4 个字节，double 则占用 8 个字节等），但程序中的每个数据只给定了一个地址。假设变量 i 的地址为 80 00H，字节 01H、23H、45H、67H 应该各有一个内存地址，那么地址 0800H 对应 4 字节中哪字节的地址呢？这就是字节排列顺序的问题了。

多字节数据都存放在连续的字节序列当中，根据数据中各字节在连续字节序列中的排列顺序不同，可以有两种方式：大端方式（bid endian）和小端方式 (little endian)

大端方式：按照最高有效字节到最低有效字节的顺序存储数据，符合人类阅读习惯。
小端方式：按照最低有效字节到最高有效字节的顺序存储数据。

也可以这样描述

大端方式：数据的低位保存在内存的高地址中，而数据的高位，保存在内存的低地中；
小端方式：数据的低位保存在内存的低地址中，而数据的高位,，保存在内存的高地址中

我们的计算机一般都是小端机，采用小端方式是有好处的，方便计算机处理。

例如下面机器代码：

400d3: 01 05 64 94 04 08       add % eax,0x8049464

4004d3：十六进制表示的地址。
01 05 43 0b 20 00：指令的机器代码。
add %eax,0x8049464：指令的汇编形式，该指令的操作数是一个立即数0x8049464。

执行指令时，从指令代码的后 4 字节取出该立即数，立即数存放的字节序列为 64H,94H,04H,08H，正好与操作数的字节顺序相反，即采用的是小端方式存储，得到 08049464H，去掉开头 0，得到值 0x8049464，在阅读小端存储方式机器代码时，注意是相反顺序，比如下面：

14.2.内存（边界）对齐

假设存储字长为 32 位，可按照字节、半字节和字寻址。对于机器字长为 32 位的计算机，数据以边界对齐方式存储，半字地址一定是 2 的整数倍，子地址一定是 4 的整数倍，这样无论所取的数据是字节、半字还是字，均可以一次取出，当存储的数据不满足上述要求时，通常填充空白字节使其符合要求，典型的以空间换时间的做法。

如下：

更多关于内存对齐的问题，可以移步这篇文章 C 语言重难点：内存对齐和位段

15.浮点数的表示

浮点表示法是指以适当的方式将比例因子表示在数据中，让小数点的位置根据需要而浮动 。这样，在位数有限的情况下，即扩大了数的表示范围，又保持了数的有效精度。例如，用定点数表示电子的质量（$9×10^{-28}g $）或太阳的质量（$ 2×3^{33}g $）是非常不方便的。

15.1.浮点数的表示格式

在小学学习科学计数时，我们知道对于： $ +302657264526 $这么长的数字可以用科学计数法表示为：

$+3.026×10^{11} $

而浮点数的表示格式与科学计数法有异曲同工之妙。

阶码：反映浮点数的表示范围及小数点的实际位置。
尾数：其数值部分的位数 $n$反映了浮点数的精度。因此，通常浮点数表示为： $N=r^{E}×M$

其中 r 是浮点数阶码的底（隐含），与尾数的基数相同（二进制中 $ r=2$），E 是阶码，是一个常用补码或移码表示的定点整数，M 是尾数，是一个常用原码或补码表示的定点小数。

因此，这种格式可以这样理解：尾数给出了一个小数（数符指明其正负性），同时阶码指明了小数点要向前（阶符为负）还是向后（阶符为正）移动几位。

$ case1: $: 例如浮点数 a 的阶码（补码）为 $ 0,01 $，尾数（补码）为$ 1.1001$，空间中存储的方式就是下面这样的：

a 的阶码对应的真值为 + 1，$尾数对应的真值为 =-( 2^{-2}+2{-3}+2^{-4})=- 0.0111 $，则 a 的真值为：$ 2^{1}×(-0.0111)=-0.111 $

$case2 $：例如 b 的阶码（补码）为 0 , 10 0,10 0,10，尾数（补码）为 $ 0.01001$，空间存储如下：

上述后面 1 被抛弃了，精度丢失。

b 的阶码对应真值为 + 2，尾数对应真值为 $ +(2^{-2}+2{5})=+0.01001 $，因此 b 的真值为： $2^{2}×(+0.01001)=+1.001 $。

15.2.浮点数尾数的规格化

15.2.1.左规和右规

可以看到，上面的 $case 2 $ 中，由于尾数位数不够，因此最后一位 1 丢失，导致该种表示方法下的浮点数精度丢失。就像我们在学习科学计数法的时候要求过的一样，尽量保证不要有$0.003×10^{13} $ 这样的形式出现，必须保证最高位是一个有效位，因为无效的 0 不但不会增加精度，反而会占用位数。

因此为了提高运算的精度，需要充分利用尾数的有效数位，通常采取浮点数规格化形式，即规定尾数的最高数位必须是一个有效值。非规格化浮点数需要进行规格化操作才能变成规格化浮点数。所谓规格化操作，是指通过调整一个非规划浮点数的尾数和阶码的大小，使非零的浮点数在尾数的最高位上保证是一个有效值。

规格化方法主要有两种：

左规：将尾数算数左移一位，阶码就减 1（基数为 2），左规可能要进行多次。

右规：当浮点数运算的结果尾数出现溢出（双符号位为 01 或 10）时，将尾数算数右移一位，阶码加 1（基数为 2 时） 的方法称为右规，右规只需进行一次。

下面是一个需要右规的例子：

15.2.2.规格化浮点数的特点

规格化浮点数的尾数 M M M 的绝对值应该满足 $ |M| $，若 r为 2，则有 $ |M| $。规格化表示的尾数形式如下：

1：原码规格化后

规格化的原码尾数，最高数值位一定是 1。

正数：形式为0.1××...×，其最大值表示为0.111...1，最小值表示为0.100...0，尾数的表示范围为 $ M (1-2^{-n}) $
负数：形式为1.1××...×，其最大值表示为1.10×××0，最小值表示为1.111...1，尾数的表示范围为 $ - M -(1-2^{-n}) $

2：补码规格化后

规格化的补码尾数，符号位与最高数值位一定相反。

正数：形式为0.1××...×，其最大值表示为0.111...1，最小值表示为0.100...0，尾数的表示范围为 $ M (1-2^{-n}) $。
负数：形式为1.0××...×，其最大值表示为1.01×××1，最小值表示为1.00...0，尾数的表示范围为 $-1 M -(+2^{-n}) $。

$ case3：$若某浮点数的阶码，尾数用补码表示，共 4+8 位：0.110;1.1110100，问如何规格化？

答：在这个例子中，阶数为 + 6，前面说过我们规定规格化的补码尾数的负数形式一定为1.0××...×，因此可以将1.1110100算数左移三位（补码的算数左移是低位补 0，算数右移是高位补 1），结果为1.010000，阶码变为 + 3。

15.3.浮点数表示范围（408 考试大纲已删除）

如下图所示，运算结果大于最大正数时称为正上溢，小于绝对值最大负数时称为负上溢，正上溢和负上溢统称为上溢。数据一旦产生上溢，计算机必须进行中断操作，进行溢出处理。

当运算结果在 0 到最小正数之间时称为正下溢，在 0 到绝对值最小负数之间时称为负下溢，正下溢和负下溢统称为下溢，数据下溢时，浮点数区域 0，计算机仅将其当做机器零处理。

16.IEEE754标准

16.1移码

16.1.1.移码回顾

本节内容涉及移码，有关移码的基础内容请移步

(计算机组成原理) 第二章数据的表示和运算 - 定点数的表示（原码、反码、补码和移码）

16.1.2.偏置值

前面我们说过：移码是在补码的基础上将符号位取反得到的。

其实移码的真正定义为：移码 = 真值 + 偏置值，只不过前面的讲述中我们的偏置值取定为了$2^{7}=128$，也即 1000 0000。所以，假如真值为 - 127，也即 1000 0001，那么其所对应的移码就是 1000 0001+1000 0000=0000 0001。其余数值也是这样，从下面的表格中可以看出，移码只是将补码的符号位取反了。

其实，偏置值也是可以设置为其他值的。比如今天我们学习的浮点数当中的 IEEE754 标准中，就用移码表示阶码，其偏置值取$ 2^{n-1}-1$，也即 0111 1111（127）。

这样的偏置值就导致移码会产生两个非常特殊的状态：1111 1111 和 0000 0000（真值 - 128 和 - 127），它们都对应无符号数 255；从真值 - 126 开始，对应无符号数 1，一直到无符号数 254 。

16.2.IEEE 754 标准

16.2.1.IEEE 754 标准格式

IEEE 754 将浮点数分为短浮点数、长浮点数和临时浮点数三类，C 语言遵循这个标准，因此它们分别对应float、double和long double。

数符：表示了整个浮点数的正负性。
阶码：采用移码表示，并且短浮点数的偏置值为 127。所以原本 8 位的移码表示的真值范围为 - 128~127，但是 127 的偏置值会使真值 - 127 和 - 128 较为特殊，其移码是全 0 和全 1，全 0 和全 1 在该标准下具有特殊作用，所以实际上 8 位的阶码表示真值的范围应该是 - 126 到 127。
尾数：注意采用原码表示。并且我们知道使用原码表示浮点需要进行规格化，也就是最高位格式应该是1.M，所以短浮点数这里尾数部分写的虽然是 23 位，但是实则是 24 位，一位暗含。

16.2.2.转换方法

我们知道移码等于真值阶码 + 偏置值，那么自然而然阶码真值 = 移码 - 偏置值。因此 IEEE 754 标准中，规格化的短浮点数和长浮点数的真值分别为：
$ (-1)^{s}×1.M×2{E-127} $

$ (-1)^{s}×1.M×2{E-1023} $

上式中， $s=0$ 表示正数，$ s=1$ 表示负数。

$ case:$ 将十进制数 - 0.75 转化为 IEEE 754 的单精度浮点数格式表示（十进制转换为浮点数）
答：转换步骤如下

将十进制数转化为二进制数并规格化： $ (-0.75){10} (-0.11){2} (-1.1)_{2}×2^{-1}$
确定数符号：可以看出是负数，因此数符为 1。
确定尾数部分：前面说过暗含了高位为 1，因此尾数部分是.100000...
确定阶码真值：基数指数部分是 - 1，因此阶码真值是 - 1。
确定偏移值：127
确定移码：移码 =-1+ 0111 1111=0111 1110（126，注意凑够 8 位）。
最终形式（红色是数符，蓝色是阶码，绿色是尾数）：1 01111110 10000000000000000000000000000000。

$case$：IEEE 754 的单精度浮点数 C0 A0 00 00 的值为多少 ?

答：转换步骤如下：

将十六进制转化为二进制（红色是数符，蓝色是阶码，绿色是尾数）：1100 0000 1010 0000 0000 0000 0000 0000
数符为 1：这是个负数
确定尾数部分：.01000，因此尾数真值为 $1.01_{2} $
确定移码：是10000001，可看作无符号数 129
确定偏移值：127
确定阶码真值：$阶码真值 = 移码 - 偏移值 = 1000 0001-0111 1111=(0000 0010){2} = (2){10} $
确定浮点数真值：根据公式 $ (-1)^{s}×1.M×2{E-127} $，可得真值 =$ (-1)^{1}×(1.01)_{2}×2^{129-127}$。

16.2.3.表示范围

IEEE 754 单精度浮点型表示的最小绝对值和最大绝对值。

最小绝对值：尾数全为 0，阶码真值最小为 - 126，对应机器数为 0000 0001，此时整体的真值为 $(1.0)_{2}×2^{-126}$
最大绝对值：尾数全为 1，阶码真值最大为 - 127，对应机器数为 1111 1110，此时整体的真值为$ (1.111....11)_{2}×2^{127} $。

当然即便这样，还是有溢出的问题的，因此前面提到的阶码全 0 和全 1 就派上用途了。

当阶码全为 0，尾数不全为 0 时，表示非规格化小数，也即$ (+/-)(0.××××)_{2}×2^{-126} $，阶码的隐含最高位为 0。
当阶码全为 0，尾数全为 0 时，表示真值正负 0。
当阶码全为 1，尾数全为 0 时，表示无穷大（正负）。
当阶码全为 1，尾数不全为 0 时，表示非数值 NaN（Not a Number），比如 0/0。

17.浮点数加减运算

17.1.以十进制下的科学计数法的加减运算为例说明浮点数加减运算

比如有浮点数 $ 9.85211×10^{{12}+9.96007×10}{10} $，其运算基本步骤如下：

1：对阶
所谓对阶就是对齐两个浮点数的阶数，由于计算机内部尾数是定点小数，所以对阶是一律向大阶看齐
也即 $ 9.85211×10^{{12}+0.0996007×10}{12} $。

2：尾数相减
也即 $ 9.9517107×10^{12} $。

3：规格化
由于我们已经对阶了，所以这里就不用规格化了。

如果尾加减出现了 $ 0.0099517×10^{12} $，就需要左规；如果尾数加减出现了 $99.517107×10^{12} $时，需要右规。

4：舍入
假如规定了机器只能保持 6 位有效尾数，则 $ 9.9517107×10^{12}$中多余尾数部分应该砍掉，也即 $ 9.95171×10^{12} $。

也可以采用四舍五入，也即 $9.95171×10^{12} $。
也可以采用 “若砍掉部分非 0，则入 1” 的原则，即 $ 9.95172×10^{12}$。

5：判溢出
假如规定了阶码不能超过两位，若运算后的阶码超出范围则溢出。比如 $ 9.85211×10^{{99}+9.96007×19}{99}=19.81218×10^{99} $，规格化后并采用四舍五入原则保留 6 位尾数得：$ 1.98122×10^{100} $，因此这里产生了溢出。

需要注意的是尾数溢出并不是真正的溢出，因为有可能通过规格化来拯救。

17.2.浮点数的加减运算（不舍入）

$ case$：已知十进制数 $X=-\frac{5}{256}$、 $ Y=+ $，按机器补码浮点运算规则计算$ X-Y $，结果用二进制表示，浮点数格式如下：

阶符 2 位、阶码 2 位、数符 2 位、尾数 9 位。

预备步骤 1：格式转换

对于$ X=-$：其中分子 $ (101)_{2}$，而 $ =2^{-8} $，因此 $ X=-101× 2^{{-8}=-0.101×2}{-5}=-0.101×2^{-101} $
对于 $Y=+ $：其中分子 $ 59=(111011)_{2} $，而 $ =2^{-10} $，因此 $ Y=+111011×2^{{-10}=+0.111011×2}{-4}=+0.111011×2^{-100} $。

预备步骤 2：确定浮点数

题目规定：阶符 2 位、阶码 2 位、数符 2 位、尾数 9 位。

①：对于 $X$

阶码：其阶码部分为 $-5 $，对应原码为 $ 1101 $，对应补码为 $1011 $，因为阶符 2 位、阶码 3 位，因此必须增添 1 位，采用双符号位，也即补码为 11011 11011 11011;
尾数：其尾数部分为$-0.101 $，对应原码为 $ 1.101 $，对应补码为$ 1.011 $, 因为数符 2 位、尾数 9 位，因此必须增添 1 位，采用双符号位，也即补码为$ 11.011 $, 再进行符号扩展，也即补码为 $11.011000000$。

因此 $X$ 的浮点数形式为：11011，11.011000000。

②：对于 $Y$

阶码：其阶码部分为 $-4 $，对应原码为 1100，对应补码为 $1100 $，因为阶符 2 位、阶码 3 位，因此必须增添 1 位，采用双符号位，也即补码为 $11100 $
尾数：其尾数部分为$+0.111011$, 对应原码为 $ 0.111011 $，对应补码为$ 0.111011 $，因为数符 2 位、尾数 9 位，因此必须增添 1 位，采用双符号位，也即补码为 $ 00.111011 $，再进行符号扩展，也即补码为 $00.111011000 $。

因此 $Y$ 的浮点数形式为：11100，00.111011000。

第一步：对阶：使两个数的阶码相等，小阶向大阶看齐。

求阶差（减法采用加法实现）：$ [E]_{补}=11011+00100=11111 $，也即 11001 11001 11001，也就是 $− 1 $，这意味着 $X$ 的阶数要比 $Y$ 低一阶。
对阶 (小的对齐，尾数每右移一位，阶码就加 1)：因此 $X$ 尾数部分右移一位，同时注意阶码部分 + 1，也即 11011，11.011000000----->11100，11.101100000。

第二步：尾数相减：

先求出 - $Y$：$ [-Y]_{补}=11100,11.000101000$。
再尾数相减：因此尾数部分 $ X-Y=11.101100000+11.000101000=10.110001000 $（根据之前我们学习的双符号位的运算规则，大家可以发现此时其实已经溢出了），因此 $ X-Y=11100,10.110001000 $。

第三步：规格化：

尾数采用双符号位的好处就是，我们可以通过右规的操作挽救刚才的溢出 ，算数右移时小数点前的 0 会被移动到小数点后面，补多少看双符号位的高位，因为双符号位的高位表示的是正确的本应该得到的符号，因此这里补 1，同时右移不要忘记啊阶码 + 1。

因此：11100，10.110001000----->11101，11.011000100

第四步：舍入：

这个例子中算数右移时, 抛弃了最低位的 0，0 对精度没有任何影响，因此不舍入（后面会有一个需要舍入的例子）。

第五步：判断溢出：

由于阶码采用双符号位，因此我们只需要让其 + 1，如果相同那么没有溢出，在这个例子中很明显没有溢出。

收尾步骤：翻译真值

$X-Y= 11101,11.011000100$

阶码：$ 2^{-3} $
尾数： $ -0.1001111 $

因此 $ 2 X-Y=2^{-3}×(-0.1001111)_{2}$

17.3.浮点数的加减运算（舍入）

前面的所有例子中都没有涉及到舍入这个步骤。浮点数加减运算舍入有两种：

舍 “0” 入“1”：类似于十进制中的四舍五入，即在尾数右移时，被移去的最高数位为 0，则舍去；被移去的最高数值位为 1，则在尾数的末位加 1，这样做可能会使尾数又溢出，此时需要再做一次右规。

比如某次尾数相减结果：$X-Y=11100,10.110001011 $，此时产生溢出，接着进行右规结果为 11101,11.011000101 1(抛弃)，由于这一位抛弃的是 1，因此再继续加 1，正确结果就为 11101,11.011000110 1(抛弃)（如果加上之后还要进位，可能导致又溢出，再进行右规即可）；如果舍弃的是 0 就不用加了。

恒置 “1” 法：尾数右移时，不论丢掉的最高数值位是 “1” 还是“0”，都使右移后的尾数末尾恒置为“1”。这种方法同样有可能使尾数变大或变小。

17.4.浮点数强制类型转换

C 语言中的float和double类型分别对应于 IEEE 754 单精度浮点数和双精度浮点数。long double 类型对应于扩展双精度浮点数，但是long double的长度和格式会随编译器和处理器类型的不同而与所不同。

在 C 程序中等式的赋值和判断常会强制类型转换，以下两种最为常见，其最前到后范围和精度都从小到大，转换过程没有损失

char->int->long->double
float->double

从int转换为float时，虽然不会发生溢出，但是int可以保留 32 位，float保留 24 位，可能有数据舍入；若int转换为double则不会出现这种情况。
从int或 float 转化为double时，由于double有效位数更多，因此能够保留精度。
从double转换float时，由于float表示的范围更小，因此可能发生溢出。此外，由于有效位数变少，因此可能被舍入。
从float或double转换为 int 时，由于int没有小数部分，所以数据可能会向 0 方向被截断（仅保留整数部分），影响精度，同时由于int的表示范围更小，因此可能发生溢出。

类型转换是一个让人很恼火的话题，如果处理不正确，极容易出现 bug。