第二章-数据的表示和运算

reallylearning2026/7/12大约 33 分钟

第二章-数据的表示和运算

第二章：数据的表示和运算

一、进位计数制

1.进制计数法

基数：每个数码位所用到的不同符合的个数。

$R$ 进制的基数是 $R$
位权：指的是数制中每个数位所对应的 “权重”，它与该数位的位置相关。
对于基数为 R 的数制，小数点左边第 $n$ $n$ 位（从 0 开始计数）的位权为 $R^n$ $R^{n}$ ，小数点右边第 $m$ $m$ 位的位权为 $R^{−m}$ $R^{- m}$
对于 $R$ $R$ 进制：基数 = $R$ $R$ ，每个数码位可能出现 $R$ $R$ 种字符，逢 $R$ $R$ 进 $1$ $1$
计算机使用二进制的原因：
1. 可使用两个稳定状态的物理器件表示
2. 0，1 正好对应逻辑假、真。方便实现逻辑运算
3. 可以很方便地使用逻辑门电路实现算术运算

2. 其他进制转十进制

$R$ 进制数的数值 = 各数码位与位权的乘积之和，即（ $R$ 进制转十进制公式）：

\begin{align*} &\quad \;K_nK_{n-1}\dots K_0K_{-1}\dots K_{-m} \\ &= K_n \times R^n + K_{n-1} \times R^{n-1} + \dots + K_0 \times R^0 + \\ &\quad K_{-1} \times R^{-1} + \dots + K_{-m} \times R^{-m} \end{align*}

二进制转十进制：

\begin{align*} & \quad \;(10010010.110)_2 \\ &= 1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 + 1 \times 2^{-1} + 1 \times 2^{-2} + 0 \times 2^{-3} \\ &= 128 + 0 + 0 + 16 + 0 + 0 + 2 + 0 + 0.5 + 0.25 + 0 \\ &= (146.75)_{10} \end{align*}

八进制转十进制：

\begin{align*} (345.6)_8 &= 3 \times 8^2 + 4 \times 8^1 + 5 \times 8^0 + 6 \times 8^{-1} \\ &= 192 + 32 + 5 + 0.75 \\ &= (229.75)_{10} \end{align*}

十六进制转十进制：

\begin{align*} (1A3.F)_{16} &= 1 \times 16^2 + A \times 16^1 + 3 \times 16^0 + F \times 16^{-1} \\ &= 256 + 160 + 3 + 0.9375 \\ &= (419.9375)_{10} \end{align*}

3. 二、八、十六进制互转

二进制转八进制：3 位一组，每组转换成对应的八进制符号
二进制转十六进制：4 位一组，每组转换成对应的十六进制符号
八进制转二进制：每位八进制对应 3 位二进制
十六进制转二进制：每位十六进制对应 4 位二进制
对于八、十六进制转二进制凑不够的位数进行补位：
- 整数部分高位补 0
- 小数部分低位补 0

十进制（Decimal, D）	二进制（Binary, B）	八进制（Octal, O）	十六进制（Hexadecimal, H）
0	0000	0	0
1	0001	1	1
2	0010	2	2
3	0011	3	3
4	0100	4	4
5	0101	5	5
6	0110	6	6
7	0111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F

4. 十进制转其他进制

整数部分：除基取余法，先取得的 “余” 是整数的低位
小数部分：乘基取整法，先得到的 “整” 是小数的高位。有的小数无法用二进制精确表示
将十进制数 $158.5$ 转换为二进制：
整数部分采用 除基取余法 （这里的基数是 2），倒序排列余数：
$\begin{align*} 158 \div 2 &= 79 \quad \text{余} \quad 0 \quad (a_0=0) \\ 79 \div 2 &= 39 \quad \text{余} \quad 1 \quad (a_1=1) \\ 39 \div 2 &= 19 \quad \text{余} \quad 1 \quad (a_2=1) \\ 19 \div 2 &= 9 \quad \text{余} \quad 1 \quad (a_3=1) \\ 9 \div 2 &= 4 \quad \text{余} \quad 1 \quad (a_4=1) \\ 4 \div 2 &= 2 \quad \text{余} \quad 0 \quad (a_5=0) \\ 2 \div 2 &= 1 \quad \text{余} \quad 0 \quad (a_6=0) \\ 1 \div 2 &= 0 \quad \text{余} \quad 1 \quad (a_7=1) \\ \end{align*}$
倒序排列余数得： $(158)_{10} = (10011110)_2$
小数部分采用 乘基取整法 ，顺序排列整数部分：
$\begin{align*} 0.5 \times 2 &= 1.0 \quad \lfloor 1.0 \rfloor = 1 \quad (b_{-1}=1) \\ 0.0 \times 2 &= 0.0 \quad \lfloor 0.0 \rfloor = 0 \quad (\text{终止}) \\ \end{align*}$
顺序排列整数得： $(0.5)_{10} = (0.1)_2$
将整数部分与小数部分合并： $(158.5)_{10} = (10011110.1)_2$
十进制转二进制也可以用拼凑法

指数（ $2^n$ ）	值	指数（ $2^n$ ）	值
$2^{-3}$	0.125	$2^5$	32
$2^{-2}$	0.25	$2^6$	64
$2^{-1}$	0.5	$2^7$	128
$2^0$	1	$2^8$	256
$2^1$	2	$2^9$	512
$2^2$	4	$2^{10}$	1024
$2^3$	8	$2^{11}$	2048
$2^4$	16	$2^{12}$	4096

5. 真值和机器数

真值：符合人类习惯的数字
机器数：数字实际存到机器里的形式，正负号需要被 “数字化”（0表示正，1表示负）

真值（十进制）	机器数（8位二进制补码）
+15	`00001111`
-8	`11111000`

二、定点数的编码表示

定点数：小数点的位置固定不变（ $996.007$ ）
浮点数：小数点的位置不固定（ $9.96007×10^2$ ）
定点数的表示：

无符号数：整个机器字长的全部二进制位均为数值位，没有符号位，相当于数的绝对值。
有符号数：原码、反码、补码、移码

1. 无符号数

无符号数：

整个机器字长的全部二进制位均为数值位，没有符号位，相当于数的绝对值。
通常只有无符号整数，没有无符号小数
$n$ 位的无符号数表示范围： $0$ ~ $2^n-1$
8 位二进制无符号数表示范围： $2^8-1=255$ 种

2. 有符号数

每个有符号数包括符号位和数值部分：

符号位：0 表示正、1 表示负
数值部分：也称为 “尾数”，若机器字长为 $n$ 位，则尾数占 $n-1$ 位
保存一个小数需要把整数部分和小数部分单独保存
定点整数：小数点隐含在最低位的后面，最高位为符号位
定点小数：小数点隐含在符号位的后面，最高位为符号位
若真值为 x，可用原码（[x]_原）、反码（[x]_反）、补码（[x]_补）三种方式来表示定点整数和定点小数，还可以用移码（[x]_移）表示定点整数

Ⅰ. 原码

原码：用尾数表示真值的绝对值，符号位 “0/1” 对应 “正/负”
定点整数原码：

若机器字长为 $n+1$ 位，原码整数的表示范围（关于原点对称）： $-(2^n-1)≤x≤2^n-1$
真值 $0$ 有 $+0$ 和 $-0$ 两种形式

真值（十进制）	原码（8位二进制）	说明
+19D	`00010011`	符号位为 0（正数），数值部分为 19 的二进制 `10011` ，高位补 0 凑满 8 位。
-19D	`10010011`	符号位为 1（负数），数值部分与 +19 相同（ `10011` ），高位补 0 凑满 8 位。

若机器字长为 8 位，-19 的原码可写为 [x]_原= 1,0010011 。
若未指明机器字长，也可写为 [x]_原= 1,10011

定点小数原码

若机器字长为 $n+1$ 位，原码小数的表示范围（关于原点对称）： $-(1-2^{-n})≤x≤1-2^{-n}$

真值（十进制）	原码（8位二进制）	说明
+0.75D	`01100000`	符号位为 0（正数），小数部分为 0.75 的二进制 `11` ，低位补 0 凑满 8 位。
-0.75D	`11100000`	符号位为 1（负数），小数部分与 +0.75 相同（ `11` ），低位补 0 凑满 8 位。

若机器字长为 8 位，-0.75 的原码可写为 [x]_原= 1.1100000 。

Ⅱ. 反码

若符号位为 $0$ ，则反码与原码相同
若符号位为 $1$ ，则数值位全部取反
反码与原码的位数和表示范围一一对应，因此 $0$ 也有两种形式

真值	原码	反码
+0D	0,0000000	0,0000000
-0D	1,0000000	1,1111111
+19D	0,0010011	0,0010011
-19D	1,0010011	1,1101100
+0.75D	0.1100000	0.1100000
-0.75D	1.1100000	1.0011111

反码只是原码转变为补码的一个中间状态，实际中并没有什么用

Ⅲ. 补码

正数的补码 = 原码
负数

原码转补码：补码 = 原码取反，末位加一（反码末位 + 1，符号位不变）
补码转原码：原码 = 补码取反，末位加一（方法一样，符号位不变）
补码转原码更快的方法：最右边的 1 及其右边同原码，最右边的 1 的左边做转换反码操作
[x]_补转 [-x]_补：符号位、尾数全部取反，末位加一
补码的 0 只有一种表示，即 00000000 ，因此规定补码 1,0000000 = $-2^7$ $- 2^{7}$ ，补码 1.0000000 = $-1$ $- 1$
- 若机器字长为 $n+1$ 位，补码整数的表示范围（比原码多表示一个 $-2^n$ ）： $-2^n≤x≤2^n-1$
- 若机器字长为 $n+1$ 位，补码小数的表示范围（比原码多表示一个 $-1$ ）： $-1≤x≤1-2^{-n}$

真值	原码	反码	补码
+0D	0,0000000	0,0000000	0,0000000
-0D	1,0000000	1,1111111	0,0000000
+19D	0,0010011	0,0010011	0,0010011
-19D	1,0010011	1,1101100	1,1101101
+0.75D	0.1100000	0.1100000	0.1100000
-0.75D	1.1100000	1.0011111	1.0100000

补码的作用：使用补码可将减法操作转变为等价的加法，ALU 中无需集成减法器。执行加法操作时，符号位一起参与运算

Ⅳ. 移码

移码：在补码的基础上将符号位取反。
移码只能用于表示整数
移码和补码是一一对应的，因此表示范围与补码一样。
相比于补码的优势：表示的整数很方便对比大小

3. 类型转换

C 语言中定点整数（int、short、long）是用补码的形式存储的
无符号数与有符号数：

不改变数据内容，改变解释方式

// x = 1110 1111 0001 1111，y = 1110 1111 0001 1111
short x = -4321;
// 真值 x = -4321，y = 61215
unsigned short y = (unsigned short)x;

长整数变短整数：

高位截断，保留低位

// a = 0x000286a1
// b = 0xffff7751
int a = 165537, b = -34991;
// c = 0x86a1, d = 0x7751
short c = (short)a, d = (short)b;

短整数变长整数：

有符号数（符号扩展）：用符号位扩展高位（比如负号的符号位是 1，高位就补 1）
0,1011010 → 0,00000000 1011010
无符号数（零扩展）：高位补 0
01011010 → 00000000 01011010

长度扩展的应用场景：

ALU 的位数是固定的，运算前可能需要把短数据扩展为长数据
通用寄存器位数是固定的，把数据存入寄存器时，可能需要进行长度扩展
主存内的各种数据长度不一，有时需要把短数据扩展为长数据

三、数字电路

1. 逻辑门电路

逻辑门电路：用于处理二进制的逻辑运算

基本逻辑运算
与运算（AND）
规则：所有输入全为1，输出才为1；任意输入为0，输出为0。
表达式： $Y=A·B$
或运算（OR）
规则：任意一个输入为1，输出即为1；全部输入为0，输出才为0。
表达式： $Y=A+B$
非运算（NOT，取反）
规则：输入与输出完全相反，输入1输出0，输入0输出1。
表达式： $Y=\overline{A}$
复合逻辑运算（由基本运算组合得到）
1. 与非：先做与运算，再整体取反
2. 或非：先做或运算，再整体取反
3. 异或：两个输入不相同（一个0一个1）时输出1；输入相同输出0
4. 同或（异或非）：异或运算结果取反；两个输入相同时输出1，输入不同输出0
异或运算的应用：奇偶校验、二进制加法

多输入门电路：

多输入或门： $Y=A+B+C+D$ ，当且仅当所有输入都为 0 时，输出才为 0（有 1 则 1 ）
多输入与门： $Y=A·B·C·D$ ，当且仅当所有输入都为 1 时，输出才为 1（全 1 才 1 ）
多输入或非门： $\overline{Y}=\overline{A+B+C+D}$ ，当且仅当所有输入都为 0 时，输出才为 1（全 0 才 1 ）
多输入与非门： $\overline{Y}=\overline{A·B·C·D}$ ，当且仅当所有输入都为 1 时，输出才为 0（有 0 则 1 ）
逻辑运算优先级

非 > 与 > 或
有括号先算括号
非运算下面隐含一个括号

2. 多路选择器

多路选择器（Multiplexer，MUX）：在多个输入数据中，只允许其中一个数据通过 MUX，类似于电路的 “守门员”。

若有 $k$ 个输入，则控制信号的位数 $m≥⌈log_2k⌉ \text{ bit}$
有的多路选择器可能会预留一个控制信号，用于拦截所有输入

3. 三态门

三态门：根据控制信号决定是否让输入的数据通过。
三态门的控制信号通常只需要 1 bit，op = 1 表示允许数据通过，op = 0 表示不允许数据通过。

四、加法器

1. 一位全加器

一位全加器（FA，Full Adder），即只进行 1 bit 的加运算

本位：进行运算的位
进位：低位的加法溢出产生进位
封装后的一位全加器 FA：
设被加数本位 $A_i$ ，加数本位 $B_i$ ，来自低位的进位 $C_{i-1}$ ，本为和 $S_i$ ，向高位的进位 $C_i$
本为和：输入中有奇数个 1 时输出 1

S_i=A_i\oplus B_i \oplus C_{i-1}

向高位的进位：输入中至少 2 个 1 时输出 1

C_i=A_iB_i+(A_i \oplus B_i)C_{i-1}

一位全加器的逻辑结构
一位全加器的逻辑符号

2. 并行加法器

并行加法器：两个输入端允许并行输入 n bit 进行加法运算

串行进位
- 实现：将 n 个一位全加器简单串联，可支持 n bit 并行加
- 缺点：进位信息是串行产生的，运算速度较慢
并行进位
- 实现：对 “串行进位” 的加法器电路进行优化，增加 CLA（Carry-Lookahead Adder，先行进位加法器）部件
- 优点：进位信息是并行产生的，运算速度更快

3. 带标志位的加法器

在并行加法器的基础上，增加电路逻辑，输出 OF、SF、ZF、CF 等标志位

标志位	翻译	作用	含义
OF	Overflow Flag，溢出标志	判断带符号数加减运算是否溢出	1 溢出、0 未溢出
SF	Sign Flag，符号标志	判断带符号数加减运算结果的正负性	1 负 0 正
ZF	Zero Flag，零标志	判断加减运算结果是否为 0	ZF = 1 表示运算结果为 0
CF	Carry Flag，进位/借位标志	判断无符号数加减运算是否溢出	1 溢出、0 未溢出

每个标志的运算规则：

OF，即最高位的进位 $\oplus$ 次高位的进位

OF=C_n \oplus C_{n-1}

SF，取运算结果的最高位（符号位）

SF=S_n

ZF，仅当运算结果所有 bit 全 0 时，ZF 才为 1，此时表示运算结果为 0

‾ZF=\overline{S_n+…+S_2+S_1}

CF，反映无符号数加减运算是否溢出

CF=C_{out} \oplus C_{in}=Sub \oplus C_{out}

4. 补码加减运算电路

Sub（Substration）加减法控制信号
加法 Sub = 0 ，此时 MUX 选通 0。然后通过加法器按位相加
减法 Sub = 1 ，此时 MUX 选通 1，且 Cin = 1 。即减数全部按位取反，末位 + 1，减法变加法。

五、算术逻辑单元 ALU

1. ALU 的作用

CPU 由控制器、运算器组成：

控制器负责解析指令，并根据指令功能发出相应的控制信号
运算器负责对数据进行处理，如加减乘除等
ALU（Arithmetic and Logic Unit，算术逻辑单元）是一种组合逻辑电路，实现了算术运算（加减乘除）、逻辑运算（与或非）等功能。因此ALU 是运算器的核心
由于加减乘除等运算都要基于 “加法” 来实现，因此加法器是 ALU 的核心

组合逻辑电路与时序逻辑电路总结笔记

一、组合逻辑电路（不包含寄存器）

核心特点：输出仅由当前输入决定，输入变化输出立刻同步改变，不具备记忆存储能力
通俗举例：电灯开关，开关状态（输入）直接决定灯亮灭（输出），和过往操作无关
常见典型电路：加法器、编码器（如键盘按键实时转二进制编码）

二、时序逻辑电路（包含寄存器）
4. 核心特点：输出由当前输入 + 过往历史状态共同决定，具备记忆功能
5. 通俗举例：自动售货机，会累计记录之前投币总额，结合本次操作判断是否出货
6. 常见典型电路：计数器、各类存储器（例如主板时钟断电仍可维持时间记录）

2. ALU 的功能

算术运算：加、减、乘、除等
逻辑运算：与、或、非、异或、移位等
其他：求补码、直送等
如上，总共支持 $k$ 种功能，那么控制信号位数 $m ≥ ⌈log_2k⌉$
ALU 最简单的实现原理：多个功能电路 + MUX，通过控制信号选通 MUX 的某个线路

3. ALU 图示

输入：

控制信号 op（Operation）：由控制器产生，控制 ALU 进行指定运算，占 $m$ bit
m 的取值：如果ALU 支持 $k$ 种功能，则控制信号位数 $m ≥ ⌈log_2k⌉$
ALU 的运算数、运算结果位数与计算机的机器字长相同
或其他输入信息（如来自更低位的进位信息 Cin）
输出：
$n$ bit 的输出结果 F与计算机机器字长相同
ZF/OF/SF/CF标志位，用于表示本次运算结果的特征，这些标志信息通常会被送入 PSW（程序状态字寄存器，但有时也称为标志寄存器 FR，Flag Register）
或其他输除信息（如往更高位的进位信息 Cout）

六、定点数移位运算

移位运算：通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权
应用：可以通过移位运算快速实现特殊数值的乘法、除法

1. 逻辑移位

逻辑移位常用于处理无符号整数
逻辑左移：高位移出丢弃，低位补 0

每逻辑左移 $r$ 位，则相当于 $×2^r$
溢出判定：若逻辑左移丢弃的位 $=1$ ，则发生溢出（超过 n bit 无符号整数的表示范围）
逻辑右移：低位移出丢弃，高位补 0
每逻辑右移 $r$ 位，相当于 $÷2^r$
若逻辑右移丢弃的位 $=1$ ，则会丢失精度

2. 算术移位

移位操作总结

高位移出低位补，低位移出高位补
补码算数右移填1，其他移位操作全部填0
左移操作会溢出，右移操作丢失精度

算术移位常用于处理带符号整数
算术左移：高位移出丢弃，低位补 0

运算规则与逻辑左移一样
溢出判定：若算术左移前后的符号位不同，则发生溢出
算术右移：低位移出丢弃，高位补符号位
若算数右移丢弃的位 $=1$ ，则会丢失精度

七、加减运算

1. 定点数原码的加减

原码加法	被加数 + 加数	运算规则
正 + 正	绝对值做加法，结果为正，可能会溢出
负 + 负	绝对值做加法，结果为负，可能会溢出
正 + 负	绝对值大的减绝对值小的，符号同绝对值大的数
负 + 正	绝对值大的减绝对值小的，符号同绝对值大的数
原码减法：“减数” 符号取反，即可转为加法

2. 定点数补码的加减

对于补码来说，无论是加法还是减法，最后都会转变成加法，有加法器实现运算，符号位也参与运算

机器字长为 8 位，A = 15，B = -24，求 [A+B]_补和 [A-B]_补

[A]_补= 0,0001111，[B]_补= 1,1101000
[A+B]_补= [A]_补+ [B]_补= 1,1110111
[A-B]_补= [A]_补+ [-B]_补= 0,0001111 + 0,0011000 = 0,0100111

补码转原码更快的方法：最右边的 1 及其右边同原码，最右边的 1 的左边同反码（找个例子试一遍就知道了）

3. 有符号数的溢出判断

上溢：只有 “正数 + 正数” ，结果为负数，才会上溢
下溢：只有 “负数 + 负数” ，结果为正数，才会下溢
单符号位补码又称 模 2 补码 ，双符号位补码又称 模 4 补码
双符号位在存储时只存储 1 个符号位，运算时会复制一个符号位

方法一：
采用一位符号位，两个加数同号，运算结果变号，则有溢出
记 $A$ 的符号为 $A_S$ ， $B$ 的符号为 $B_S$ ，运算结果 $S$ 的符号为 $S_S$ ，则溢出逻辑表达式为

V=A_SB_S \overline{S_S} + \overline{A_S} \overline{B_S} S_S= \begin{cases} 0, & 无溢出 \\ 1, & 有溢出 \\ \end{cases}

若 $V=0$ 表示无溢出， $V=1$ 表示有溢出
2. 方法二：
采用一位符号位，根据数据位进位情况判断溢出。若符号位的进位与最高数值位的进位不同则发生溢出
记符号位的进位为 $C_S$ ，最高数值位的进位为 $C_1$ ，则

V=C_S \oplus C_1=\begin{cases} 0, & 无溢出 \\ 1, & 有溢出 \\ \end{cases}

若 $V=0$ 表示无溢出， $V=1$ 表示有溢出
3. 方法三：
采用双符号位，正数符号为 00，负数符号为 11，若运算结果的两个符号位不同则溢出
记两个符号位为 $S_{S1}、S_{S2}$ ，则

V=S_{S1} \oplus S_{S2}=\begin{cases} 0, & 无溢出 \\ 1, & 有溢出 \\ \end{cases}

若 $V=0$ 表示无溢出， $V=1$ 表示有溢出

4. 无符号数的加减

加法：从最低位开始，按位相加，并往更高位进位
减法：“被减数” 不变，“减数” 变为补数（ A-B 变为 A+(-B) ），然后就变成了加法
“减数” 全部位按位取反，末位 +1

5. 无符号数的溢出判断

手算判断溢出： $n$ bit 无符号整数表示范围 $0$ ~ $2^n-1$ ，超出此范围则溢出
加法判断溢出：最高位产生的进位 $=1$ 时，发生溢出，否则未溢出。
减法判断溢出：减法变加法，最高位产生的进位 $=0$ 时，发生溢出，否则未溢出。

八、乘除运算

1. 无符号整数乘法

基本原理：逐位相乘，错位相加

两个 $n$ bit 的无符号数的乘法，可拆解为 $n$ 轮加法运算
根据乘数的各个 bit，决定每一轮加法运算 “+ 被乘数” 或 “+ 全 0”
每一轮加法运算需要与上一轮加法运算的结果 “错位相加”
4 位简化版

运算过程：
开始：

被乘数、乘数分别放入寄存器 $X、Y$
乘积寄存器 $P$ 置为 0
计数器 $\text{Cn}$ 的初始值置为 $n$
进行 $n$ 轮处理：重复 $n$ 轮加法、移位运算，直到计数器 $\text{Cn}=0$
将乘数寄存器 Y 的最低位，送入 “控制逻辑” 进行判断
若 $Y$ 的最低位为 1，则执行加法，运算结果写回 $P$ ，加法产生的进位保存至进位触发器 $C$ ；若 $Y$ 的最低位为 0，则什么也不做
将【 $C，P，Y$ 】视为整体，逻辑右移一位
计数器 $\text{Cn}$ 减 1
结束：当计数器 $\text{Cn}=0$ 时，乘法运算结束
用 $2n$ 位【 $P，Y$ 】暂存乘法运算结果，但最终仅保留低 $n$ 位【 $Y$ 】作为最终结果，因此可能发生溢出

溢出判断：若丢弃的高 $n$ 位【 $P$ 】不全为 0，说明发生溢出，并设置OF 标志位 $=1$
溢出处理：可选择忽略乘法溢出。或选择在乘法指令之后执行一条 “溢出自陷指令”（如 x86 的 INTO_Interrupt_on_Overflow指令），当 OF = 1 时会触发 “异常处理程序” 来处理溢出

2. 带符号整数乘法

与无符号整数乘法电路的不同

可能进行加法、减法
控制逻辑根据 2 bit（ $Y$ 的最低位、辅助位）决定本轮该如何处理
低位增加一个 “辅助位”
不保存最高位产生的进位信息
4 位简化版

运算过程

前情提要：
带符号数（补码）乘法，符号位参与运算
当被乘数、乘数种有一个全为 0 时，结果直接得 0，不需要在进行后续的运算步骤

开始：

将被乘数、乘数分别放入寄存器 $X、Y$
乘积寄存器 $P$ 置为 0，“辅助位” 置为 0（辅助位就是图中的黄色块）
计数器 $\text{Cn}$ 的初始值置为 $n$
进行 $n$ 轮处理：重复 $n$ 轮加 / 减法、移位运算，直到计数器 $\text{Cn}=0$
将乘数寄存器 $Y$ 的最低位、辅助位，2 bit 送入 “控制逻辑” 进行判断
根据寄存器 $Y$ 的最低位、辅助位，决定是 “ +[x]_补 ”、“ -[x]_补 ”、“ +0 ”（记忆技巧：辅助位 - $Y$ 最低位）

寄存器 $Y$ 最低位	辅助位	本轮操作
0	0	+0
0	1	+[x]_补
1	0	-[x]_补
1	1	+0

将【 $P、Y、辅助位$ 】视为整体，算数右移一位
计数器 $\text{Cn}$ 减 1
结束：当计数器 $\text{Cn}=0$ 时，乘法运算结束
用 $2n$ 位【 $P，Y$ 】暂存乘法运算结果，但最终仅保留低 $n$ 位【 $Y$ 】作为最终结果，因此可能发生溢出

溢出判断：若 $2n$ 位的高 $n+1$ （如果是8位，那就是前面的五位）位不完全相同，说明发生溢出，并设置OF 标志位 $=1$
溢出处理与无符号整数乘法一样

3. 实现乘法运算的方式

计算机实现乘法运算的三种方式：

由 ALU、移位器、寄存器、控制逻辑组成的乘法电路（就是上面说的电路）

该电路若实现 $n$ bit 无符号数相乘，至少需要 $n$ 个时钟
改进方案：可以实现 “两位乘法”，每轮处理乘数寄存器 $Y$ 的末尾 2 bit，此时仅需 $\frac{2}{n}$ 个时钟即可完成运算

阵列乘法器

特点：可以在 1 个时钟内完成乘法运算
$4×4$ 位阵列乘法器示例图
阵列乘法器是快速乘法器种的一种。很多快速乘法器都可以在 1 个时钟内完成乘法运算

由逻辑运算（位运算、移位运算）、加 / 减运算等效实现乘法

优点：在没有乘法运算电路、不支持乘法指令的计算机中，也可以等效实现乘法效果
缺点：运算速度很慢（在非流水线计算机中，每条指令的执行都至少需要 1 个时钟）

4. 无符号整数除法

除法手算方法：逐位上商，错位相减
二进制上商规则：商 × 除数的值，要尽可能接近 “中间余数”，但又不能大于中间余数。如果中间余数 ≥ 除数，则上商 1，否则上商 0

余数的数学定义： $被除数=商×除数+余数$
除法器支持 $2n \text{ bit} ÷n \text{ bit}$ ，最终得到 $n \text{ bit}$ 商、 $n \text{ bit}$ 余数；被除数位不足 $2n$ ，需要位扩展（高位补 0）至 $2n$
无符号整数的双精度除法（ $2n÷n$ ）可能发生 “商溢出” ；
无符号整数的单精度除法（ $n÷n$ ）不可能发生 “商溢出”
4 位简化版

运算过程：
开始：
正常情况：将数据放入寄存器：

除数放入寄存器 $Y$
被除数放入寄存器【 $R、Q$ 】并完成零扩展
计数器 $\text{Cn}$ 的初始值置为 $n$
特殊情况检查：
如果除数为 0，发生 “除数为0” 异常，停止除法运算，调出操作系统的异常处理程序
如果 $|被除数|＜|除数|$ ，则商 = 0，余数 = 被除数，除法器不必再执行
进行 $1+n$ 轮处理（计算 $1+n$ 位商）

上商规则：如果【 $R$ 】-【 $Y$ 】≥ 0，则上商 1，否则上商 0
第一轮：特殊处理，商溢出判断
直接上商，若第一位商 = 1，发生“商溢出” 异常，停止除法运算
直接上手，若第一位商 = 0，说明不会发生 “商溢出”，不必保存这位商，也不让 $\text{Cn}--$ ，除法运算继续

第一位商不保存，仅用于商溢出判断

其余 $n$ 轮处理

先左移，空出的位用于上商
上商，背后的过程可能会进行加法 / 减法

比如上商是 $R-Y$ ，如果差 < 0，需要恢复余数 $R-Y+Y$

计数器 $\text{Cn}$ 减 1；当计数器 $\text{Cn}=0$ 时，除法运算结束

$n \text{ bit}$ 寄存器【 $R$ 】保存余数， $n \text{ bit}$ 寄存器【 $Q$ 】保存商

在 x86 中，除数为 0、商溢出都属于 “除法错异常”（Divide Error Exception），也可简译为 “除法异常”

九、浮点数的表示

1. 科学计数法

科学技术法由符号、尾数、基数、阶码组成

符号：决定数值的正负性
尾数：影响数值的精度。尾数的位数越多，精度越高
阶码：反映小数点的实际位置
基数： $K$ 进制通常默认基数为 $K$
规格化：确保尾数的最高位非 0 位数刚好在小数点之前

二进制科学计数法：如 $-110.11\Longrightarrow -1.1011×2^2$

2. IEEE 754

IEEE 754 —— 由 IEEE 制定的二进制浮点数算术标准，规定了在计算机内部，如何使用二进制表示和运算浮点数。

如 C 语言float 型（32 bit，单精度浮点型）、double 型（64 bit，双精度浮点型）、long double（80 bit，扩展精度浮点型）
其他：16 bit 半精度浮点型、128 bit 四倍精度浮点型
float 单精度浮点型的存储：占 32 bit = 1 bit 符号 + 8 bit 阶码 + 23 bit 尾数
符号的存储：0 正 1 负
尾数的存储：规定小数点位置在 23 bit 之前。默认存储规格化尾数，小数点前的 1 省略（隐含，因此实际可表示 24 bit）
基数不用专门存储，规定基数为 2 即可
阶码的存储：用移码表示，规定偏置值为 127 （2^8-1- 1）

如何将十进制真值转换为偏置值为

M

的移码

将十进制真值 + 偏置值
按 “无符号整数” 规则转换为指定位数
例： $2+127=129 \Longrightarrow 10000001$

double 双精度浮点型的存储：占 64 bit = 1 bit 符号 + 11 bit 阶码 + 52 bit 尾数

符号、尾数、基数与单精度浮点型一样
阶码：规定偏置值为 1023 （2^11-1- 1）

3. 表示范围

IEEE 754 标志规定：

仅当阶码不全为 0、也不全为 1 时，表示这是一个 “规格化浮点数”
阶码全为 0、全为 1 留作特殊用途，需要按照特殊的方式取解读真值
规格化（单精度）浮点数的表示范围
规格化浮点数的阶码不能全为 0 或全为 1，因此阶码取值范围是 1 ~ 254，减掉偏置值 127 后真值取值范围是 -126 ~ 127
尾数的小数点前隐含 1

说明	符, 阶, 尾	二进制	十进制
正数最小	0, 00000001, 00…00	$+1.0×2^{-126}$	$+1.0×2^{-126}$
正数最大	0, 11111110, 11…11	$+1.11...11×2^{127}$	$+(2-2^{-23})×2^{127}$
负数最小	1, 11111110, 11…11	$-1.11...11×2^{127}$	$-(2-2^{-23})×2^{127}$
负数最大	1, 00000001, 00…00	$-1.0×2^{-126}$	$-1.0×2^{-126}$

非规格化（单精度）浮点数表示范围

非规格化的阶码全 0、尾数不全为 0。因此阶码真值 =1 - 偏置值
尾数的小数点前隐含 0

说明	符, 阶, 尾	二进制	十进制
正数最小	0, 00000000, 00…01	$+0.00...01×2^{-126}$	$+2^{-23}×2^{-126}=+2^{-149}$
正数最大	0, 00000000, 11…11	$+0.11..11×2^{-126}$	$+(1-2^{-23})×2^{-126}=+(2^{-126}-2^{-149})$
负数最小	1, 00000000, 11…11	$-0.11..11×2^{-126}$	$-(1-2^{-23})×2^{-126}=-(2^{-126}-2^{-149})$
负数最大	1, 00000000, 00…01	$-0.00...01×2^{-126}$	$-2^{-23}×2^{-126}=-2^{-149}$

4. 特殊状态

（单精度）特殊状态

值的类型	符号	阶码	尾数	值	例子
正零	0	全 0	全 0	+0	正下溢
负零	1	全 0	全 0	-0	负下溢
非规格化正数	0	全 0	不全 0	$0.尾数×2^{-126}$	$00200000\text{H}=+2^{-128}$
非规格化负数	1	全 0	不全 0	$-0.尾数×2^{-126}$	$80200000\text{H}=-2^{-128}$
正无穷	0	全 1	全 0	$+∞$	正数除以 0、正上溢
负无穷	1	全 1	全 0	$-∞$	负数除以 0、负上溢
无定义数（非数）	0、1	全 1	不全 0	NaN	零除以零、负数开根号等

5. 浮点数的溢出

浮点数的上溢（Overflow）

运算结果大于最大规格化正数时称为正上溢；小于绝对值最大的规格化负数时称为负上溢

正上溢、负上溢统称为上溢，也会翻译成溢出
浮点数上溢的处理：
IEEE 754 规定，默认不响应浮点数溢出异常，不中断程序，除非程序员手动开启此类异常响应

浮点数运算部件将运算结果设为 $+∞$ 或 $-∞$
设置浮点数溢出异常标志位（如 x86 会将浮点运算单元 FPU 的 OE 标志位_Overflow_Exception置为 1）
浮点数的下溢（Underflow）

若浮点数运算结果在 0 至绝对值最小的规格化正数之间时称为正下溢，在 0 至绝对值最小规格化负数之间时称为负下溢
正下溢、负下溢统称为下溢
浮点数下溢的处理：
IEEE 754 规定，默认不响应浮点数溢出异常，不中断程序，除非程序员手动开启此类异常响应

若结果落入非规格化区间，则用非规格化浮点数存储；若结果太小（真值逼近于 0）则按机器零存储
若下溢至机器零，设置浮点数下溢异常标志位（如 x86 会将 FPU 的 UE 标志位_Underflow_Exception置为 1）

十、浮点数的加减运算

1. 对阶

目的：使两个操作数小数点对齐，阶码相等。

求阶差 $\Delta E$
原则：小阶向大阶看齐（小阶尾数右移，阶码增大）
右移时低位移出位不能丢，保留参与后续运算
❌ 若大阶向小阶看齐，尾数左移会丢失高位，结果出错

2. 尾数加减

对阶后，尾数按定点小数加减规则运算。

IEEE 754 有隐藏位，运算前需还原到尾数
运算后尾数不一定规格化，需进一步规格化处理

3. 尾数规格化

IEEE 754 规格化尾数形式： $1.xx...x$

操作	触发条件	操作	阶码变化	次数
右规	结果为 $1x.xxx$ （尾数溢出）	尾数右移1位	阶码+1	只需1次
左规	结果为 $0.0...01x$	尾数左移，第1位移到小数点左边	阶码-1	可能多次

左规一次 = ×2，右规一次 = ÷2

4. 舍入（4种模式）

对阶和右规时尾数右移丢低位，需舍入恢复精度。

就近舍入（0舍1入）：类似四舍五入，中间值选偶数
正向舍入：朝 $+\infty$ 方向舍入（取右边最近）
负向舍入：朝 $-\infty$ 方向舍入（取左边最近）
截断法：直接截取所需位，丢弃后面所有位（趋原点舍入）

溢出判断（核心考点）

关键结论

尾数溢出 ≠ 最终结果溢出，尾数溢出可通过右规纠正。
浮点数溢出由指数（阶码）是否溢出来判断。

操作	阶码变化	溢出风险	结果处理
对阶	小阶增大	无溢出	—
右规 / 舍入进位	阶码 +1	指数上溢	产生异常
左规	阶码 -1	指数下溢	按机器零处理

具体判断

指数上溢：正指数超过最大值（127 或 1023）→ 异常
指数下溢：负指数超过最小值（-149 或 -1074）→ 机器零

补充：若尾数/阶码用补码表示，可用双符号位判断溢出。

C语言中的浮点数类型

类型对应

C语言类型	IEEE 754标准
float	单精度浮点数
double	双精度浮点数
long double	扩展双精度（长度格式随编译器/处理器）

隐式类型转换（类型提升）

规则：低类型 → 高类型
char → int → long → float → double

范围和精度从小到大，转换无损失
混合运算时系统自动转换，称为隐式类型转换

int 与 float 精度和范围分析

int → float：不会溢出，但 float 尾数仅 24 位有效位，int 32位，超过24位时精度丢失，需舍入
int/float → double：double 有效位更多，能保留精确值
double → float：float 范围更小，大数可能溢出；有效位数变少，会发生舍入
float/double → int：向0方向截断（只保留整数部分），发生舍入；int 范围更小，大数可能溢出

十一、数据的存储和排列

1. 大小端模式

最高有效字节（MSB）：一个数值的最左边字节
最低有效字节（LSB）：一个数值的最右边字节
大端模式：把最高的有效字节存到更低地址部分，最低有效字节存在较高地址部分。
优点：便于人类阅读
小端模式：和大端模式反过来
优点：便于机器处理

如 4 字节 int：01 23 45 67 H
最高有效字节：01
最低有效字节：67
大端模式：01 23 45 67
小端模式：67 45 23 01

2. 边界对齐

自然对齐（边界对齐）定义：若变量占用N字节，变量起始内存地址必须能被N整除。

例子

char（1字节）：地址 % 1 = 0，任意地址都合法；
short（2字节）：地址 % 2 = 0，只能存放于偶数地址（0、2、4…）；
int（4字节）：地址 % 4 = 0，地址只能为0、4、8、12……；
long long/double（8字节）：地址 % 8 = 0，地址只能为0、8、16……。

现代计算机通常是按字节编址，即每个字节对应 1 个地址。通常也支持按字、按半字、按字节寻址

不管是按字还是按半字寻址，最终都要转换为字节地址。字、半字、字节之间的转换是逻辑移位
假设存储字长 32 位，1 字 = 32 bit，半字 = 16 bit，1 字节 = 8 bit
字节地址 = 字地址 × 2²（字地址逻辑左移 2 位得到字节地址）
每次访存只能读 / 写 1个字

十二、数的比较

部分比较和转移指令：

CMP 指令：Compare 比较
JMP 指令：jump 无条件转移
JE 指令：jump if equal 相等则跳转
JG 指令：jump if greater 大于则跳转
数的比较硬件步骤：

通过 “cmp 指令” 比较 a 和 b（ cmp a, b ），实质上是用 $a-b$
相减的结果信息会记录在程序状态字寄存器（PSW，也称标志寄存器）中

进位 / 借位标志 CF、零标志 ZF、符号标志 SF、溢出标志 OF

根据 PSW 的某几个标志位进行条件判断，来决定是否转移

je 2 ：表示 $a=b$ 时跳转到 2
jg 2 ：表示 $a>b$ 时跳转到 2
jump 2 ：不管 PSW 的各种标志位直接跳转到 2