计组-数据的表示和运算(2)

2.1 数制与编码

进位计数制

基数：每个数码位所用到的不同符号的个数，$k$ 进制的基数为 $k$
$$
k进制: a_na_{n-1}…a_{2}a_1a_0…
\
=a_nk^n+a_{n-1}k^{n-1}+…+a_2k^2+a_1k+a_0+…
$$
其中 $k$ 的次幂称之为 位权 。

二进制转八进制或者十六进制，只要按3、4位一组转换即可。

image-20260319110634661

整数：除基取余法，比如模2的结果是整数的低位

小数点：乘基取余法，比如乘2的整数是小数的高位

真值与机器数

  • 真值：实际的带正负号的数
  • 机器数：把正负号数字化的数

定点数的编码表示

  • 无符号数
  • 有符号数
    • 原码 / 反码 / 补码 / 移码

若真值为 $x$ ，则用 $[x]_{原}$ 表示原码，其它同理。

image-20260319112736776

反码：若符号位为 $1$ ，数值位全部取反。是补码的中间状态

补码：正数的补码=原码，负数的补码=反码末位+1

规定定点整数补码 $[x]_{补}=1,000…=-2^k$

小数 $[x]_{补}=1.000…=-1$

移码：在补码的基础上将符号位取反。只能用于表示整数

移码表示的整数很方便比大小

$0,000\cdots0 (-2^k)\rightarrow 1,111\cdots1(2^k-1)$

技巧：由 $[x]{补}$ 快速求 $[-x]{补}$

符号位、数值位全部取反，末位$+1$

补码的作用：

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

a-b减法操作等同 模-$|b|$ 得到 $b$ 的补数，
$$
a-b \equiv a-b+p \pmod p
$$
即计算 $2^k-b$ 即可，实际上就是对应的补码，超出部分会自动舍弃

C语言强制类型转换

C语言中的定点整数是用 “补码” 存储的。

长整数变短整数，高位截断，保留低位

零扩展、符号扩展

需要扩展的情形：

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

对无符号数（补码），使用零扩展为高位补零。

对带符号整数（补码），使用符号扩展，符号位不变，用符号位扩展高位。

2.2 运算方法和运算电路

基本逻辑运算

与、或、非、异或

image-20260319150232310

优先级：非>与>或

逻辑运算公式

分配律 $A(C+D)=AC+AD$

与运算的结合律 $ABC=A(BC)$

或运算的结合律 $A+B+C=A+(B+C)$

反演律（德摩根律）：
$$
\begin{align}
\overline{A+B}&=\overline{A}\cdot\overline{B}\
\overline{A\cdot B}&=\overline{A}+\overline{B}
\end{align}
$$
多路选择器（MUX）

在多个输入数据中，只允许其中一个数据通过MUX。

若有 $k$ 个输入，则控制信号的位数 $m\geq \lceil \log_2{k}\rceil$ bit

三态门

控制信号通常只需要 1bit 。$op=1$ 表示允许数据通过；$op=0$ 表示不允许数据通过。

加法器

一位、串行进位、并行进位加法器

image-20260319152530077

多个一位全加器（FA）串行相连得到 n bit 加法器。

不足之处：进位信息是串行产生的，计算速度取决于进位产生和传递的速度。

由于两个输入端允许并行输入，因此属于：并行加法器

由于进位信息是串行产生的，因此也属于：串行进位加法器

也可称为，串行进位的并行加法器。

因此，还有并行进位的并行加法器，其所有进位信息都是同时产生的，几乎没有延迟，比串行进位的并行加法器更快。

带标志位的加法器

OF (Overflow Flag) 溢出标志，用于判断带符号数加减运算是否溢出。也用于判断数的乘法运算是否溢出。

OF = 1 溢出； OF = 0 未溢出

SF (Sign Flag) 符号标志，用于判断带符号数加减运算结果的正负性

SF = 1 负； SF = 0 正

ZF (Zero Flag) 零标志，用于判断加减运算结果是否为 $0$ 。

ZF = 1 表示结果为 0 ，ZF = 0 则不为 0

CF (Carry Flag) 进位/借位标志，用于判断无符号数加减运算是否溢出。

CF = 1溢出，CF = 0 未溢出。

标志位的生成

image-20260319163323233

算术逻辑单元ALU

ALU: Arithmetic and Logic Unit

ALU是运算器的核心，ALU的核心是加法器。

  • 算术运算
  • 逻辑运算
  • 其它：求补码、直送等。

直送，直接送出

考试重点

  • 如果 ALU 支持 $k$ 种功能，则控制信号位数 $m\geq \lceil \log_2k\rceil$
  • ALU的运算数、运算结果位数与计算机的机器字长相同

定点数的移位运算

逻辑移位（常用于处理无符号整数）

  • 逻辑左移：高位移出丢弃，低位补 0

对于无符号整数，每逻辑左移一位，则相当于 $\times 2$

  • 逻辑右移：低位移出丢弃，高位补 0

相当于 $\div2$ 且向下取整

算术移位（常用于处理带符号整数）

  • 算术左移：高位溢出丢弃，低位补 $0$

左移后符号位不同，说明发生溢出

  • 算术右移：低位移出丢弃，高位补符号位

定点数的加减运算

原码的加减运算（了解即可）

image-20260320102119779

补码的加减运算

image-20260320102507326

溢出判断

  • 两个正数相加，可能发生上溢

  • 两个负数相加，可能发生下溢

方法一

采用单符号位，对于 $[A+B]_{补}$ ，设其符号位为 $A_S,B_S$ ，运算结果的符号为 $S_S$ ，则判断
$$
V=A_SB_S\overline {S_S} + \overline {A_S};\overline{B_S} S_S
$$
若 $V$ 为 $0$ 表示无溢出，为 $1$ 表示有溢出。

方法二

采用单符号位，判断溢出符号位的进位 $C_S$ ，最高数值位的进位 $C_1$

当 $C_S$ 和 $C_1$ 不同时有溢出
$$
V=C_S\oplus C_1
$$

Eg. 两个负数的符号位分别为 $1$ ，因此 $C_S=1$ （会被舍去），如果最高值位没有进 $1$ ，说明机器数为正数，显然发生了溢出。

方法三

采用双符号位，正数为 $00$ ，负数为 $11$ ，如果出现 $01$ ，说明发生了上溢，如果出现 $10$ ，说明发生了下溢。

实际存储时只存储一个符号位，运算时会复制一个符号位

单符号位是模2补码，双符号位是模4补码

无符号数的加减运算

加法：从最低位开始，按位相加并进位

减法：

  • “被减数不变”，”减数”全部位为按位取反、末尾+1（$2^k-a$），减法变加法

判断溢出

手算：判断数是否超过 $0\sim 2^n-1$

计算机判断溢出的方法：

  • 加法：最高位产生的进位 $=1$ 时，溢出
  • 减法：最高位产生的的进位 $=0$ 时（被$2^k$取模），说明发生溢出

补码加减运算电路

image-20260320111736112

无符号整数加减运算也可使用该电路实现

乘法除法运算

无符号整数的乘法运算原理

开始：

  1. 将被乘数、乘数分别放入寄存器 X、Y
  2. 乘积寄存器P 置为 0
  3. 计数器 $C_n$ 的初始值置为 n （n 为乘数的位数）
image-20260320161234667

image-20260320161811565

带符号整数的乘法运算原理

手算时，直接用十进制算即可。

image-20260320174631389

本节的“补码一位乘法”，又被称为 布斯(Booth)乘法

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

改成两位乘法，每次处理 $2bit$

阵列乘法器

  • 可以在一个时钟内完成乘法运算
  • 是快速乘法器的一种

如果在软件上用逻辑运算、加减运算等效实现乘法，好处是可以在没有乘法运算电路、不支持乘法指令的计算机种使用，但运算速度很慢。

无符号整数的除法运算原理

无符号整数除法的手算方法

二进制上商规则： 如果中间余数 $\leq$ 除数，则上商 $1$ ，否则上商 $0$ 。

image-20260904161629760

带符号整数（补码）的除法运算原理

image-20260904162403921

2.3 浮点数的表示与运算

浮点数的表示

浮点数的表示__IEEE754

这里采用IEEE754标准

规格化：确保位数的最高位非 0 数位刚好在小数点之前

C语言float型：

符号位 1bit，阶码 8bit，尾数 23bit

符号：0 正 1 负

尾数：影响数值的精度，规定小数点位置在23bit之前。默认存储规格化尾数，小数点前的 1 省略（隐含）

阶码：反映小数点的实际位置，用移码表示，规定偏置值位 127（$2^8-1$）

基数：规定基数为 2，无需存储

将十进制真值转换为偏置值为M的移码：

将十进制真值+偏置值

按“无符号整数”规则转换为指定位数

C语言double型：

符号位 1bit，阶码 11bit，尾数 52bit

偏置值为 1023（$2^{11}-1$）

浮点数表示范围、几种特殊状态

IEEE 754标准规定：仅当阶码不全为0、也不全为1时，表示这是一个“规格化浮点数”，阶码全为0、全为1 留作特殊用途。

image-20260904184800847

单精度浮点数的阶码的真值取值范围为 $-126 \sim 127$ （去掉全0的-127与全1的128）

image-20260904185719767

image-20260904190900911

绝对值最小的 float 非规格化负数：

$-1.0\times 2^{-149}$ $1,00000000,00..001$

绝对值最小的 float 非规格化正数：

$+1.0\times 2^{-149}$ $0,00000000,00..001$

浮点数的加减运算

image-20260905161106787

浮点数的“上溢”

image-20260905161819747

同理，发生下溢时，阶码为全1，强制尾数置为全0。

数据的存储与排列

大小端模式

image-20260905162235367

边界对齐

image-20260905162740199