数据如何在计算机中表示？

运算器如何实现数据的算数逻辑运算？

2.1 数据的表示和运算

2.1.1 进位计数制及其相互转换

进制

古印度人发明的阿拉伯数字及十进制：符号反映权重，符号所在位置也反映权重
推广： $r$ 进制计数法

= + K_{n} K_{n - 1} \dots K_{2} K_{1} K_{0} K_{- 1} K_{- 2} \dots K_{- m} K_{n} \times r^{n} + K_{n - 1} \times r^{n - 1} + \dots K_{2} \times r^{2} + K_{1} \times r^{1} + K_{0} \times r^{0} K_{- 1} \times r^{- 1} + K_{- 2} \times r^{- 2} + \dots K_{- m} \times r^{- m}

基数：每个数码位所用到的不同符号的个数 ^[如十进制中共用到了 $0 \sim 9$ 共10个数字]， $r$ 进制的基数为 $r$
二进制最适合计算机表示
- 可使用两个稳定状态的物理器件表示
- 0/1正好对应逻辑值的假/真，方便实现逻辑运算
- 可以很方便地使用逻辑门电路实现算数运算

各种进制常见书写方式

二进制： $(1010001010010)_{2}$ ， $1010001010010 B$
八进制： $(1652)_{8}$ ， $1652 O$ ， $01652$
十六进制： $(1652)_{16}$ ， $1652 H$ ， $0 X 1652$
十进制： $(1652)_{10}$ ， $1652 D$

$r$ 进制->十进制

$r$ 进制：

= + K_{n} K_{n - 1} \dots K_{2} K_{1} K_{0} K_{- 1} K_{- 2} \dots K_{- m} K_{n} \times r^{n} + K_{n - 1} \times r^{n - 1} + \dots K_{2} \times r^{2} + K_{1} \times r^{1} + K_{0} \times r^{0} K_{- 1} \times r^{- 1} + K_{- 2} \times r^{- 2} + \dots K_{- m} \times r^{- m}

十进制-> $r$ 进制

分为整数部分和小数部分处理
- 整数部分->除基取余：不断除以基数 $r$ 并取余，得到的 $K_{i}$ 由低位到高位
- 小数部分->乘基取整：不断乘以基数 $r$ 并取整，得到的 $K_{i}$ 由高位到低位
直接使用拼凑法，如 $166.3125 = 128 + 32 + 4 + 2 + 0.25 + 0.0625 = 2^{7} + 2^{5} + 2^{2} + 2^{1} + 2^{- 2} + 2^{- 4}$ ，则 $(166.3125)_{10} = (1010 0110.0101)_{2}$

例题：求十进制数166.3125对应的八进制

答案： $(166.3125)_{10} = (246.24)_{8}$

二进制<->八进制、十六进制

二进制<->八进制：3位的二进制对应1位的八进制。整数部分不全则最高位用 $0$ 填充，小数部分不全则最低位用 $0$ 填充。
二进制<->十六进制：4位的二进制对应1位的十六进制。整数部分不全则最高位用 $0$ 填充，小数部分不全则最低位用 $0$ 填充。

真值与机器数

真值：符合阅读习惯的数字，如+15，-8
机器数：数字实际存到机器里的形式，需要增加一位用来表示正负号，0表示正，1表示负，如：0 1111，1 1000

2.1.2 BCD码

十进制编码

打开 PDF

BCD：Binary-Coded Decimal，用二进制编码的十进制，4个二进制位表示1个十进制位，因此会有6个冗余状态
无说明时，默认BCD码为8421码

8421码

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

使用8421码表示的数字进行算术运算的方式是先按照二进制的方式进行运算，若最后结果不在映射表中，即落在没有定义的 $1010$ 到 $1111$ 中，就直接加上 $6$ （因为有六位无效，所以加上六位跳过无效的位数）从而向前面一个数字段进一位加一，高位补全 $0$ 。每个段对应的数值合在一起就是原来的结果。 ^[例： $5 + 8 = 0101 + 1000 = 1101 = 13$ ，不在映射表中，则对 $1101$ 进行二进制的加 $6 D = 0110$ ，即计算 $1101 + 0110 = 10011$ ，补齐得到 $00010011$ ，而按照 $8421$ 码，最高位的 $0001$ 不再代表权值 $16$ ，而代表十位的 $1$ ，而后面是 $3$ ，从而组合在一起就代表了 $13$ 。]
8421码是一种有权码，四位二进制码的权值分别是8 4 2 1

余3码

0	1	2	3	4	5	6	7	8	9
0011	0100	0101	0110	0111	1000	1001	1010	1011	1100

余3码=8421码 $+ (011)_{2}$
余3码是一种无权码，各个二进制位没有固定权值

2421码

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	1011	1100	1101	1110	1111

2421码是一种有权码，四位二进制码的权值分别是2 4 2 1

2.1.4 定点整数的表示

打开 PDF

无符号整数的表示和运算

无符号数不涉及小数。无符号整数，即自然数，0、1、2、…

C语言中的无符号整数

unsigned short a=1;		//无符号整数（短整型，2B）
unsigned int b=2;		//无符号整数（整型，4B）

计算机硬件能支持的无符号整数位数是有上限的，即机器字长
全部二进制位都是数值位，没有符号位，第 $i$ 位的位权是 $2^{i - 1}$
$n$ bit无符号整数表示范围为 $0 \sim 2^{n} - 1$ ，超出则溢出，意味着该计算机无法一次处理这么多

无符号整数运算法则

加法运算：从最低位开始，按位相加，并往更高位进位
减法运算：被减数不变，减数全部位按位取反，末位+1，减法变加法

带符号整数的表示和运算

带符号整数，即整数，-2，-1，0，1，2、…
定点整数：最高一位是符号位， $0$ 是正， $1$ 是负，小数点位置一般隐含在最后。

原码

最高位为符号位，剩余的数值位表示真值的绝对值
常见书面写法： $x = - 19$ ，则 $[x]_{原} = 1, 0010011$ ，若未指明机器字长，也可写为 $[x]_{原} = 1, 10011$ 。逗号仅为了标注正负号，本身并不存在
若机器字长 $n + 1$ 位，则带符号整数的原码表示范围为： $- (2^{n} - 1) ⩽ x ⩽ 2^{n} - 1$
真值 $0$ 有两种形式： $+ 0$ 和 $- 0$ ， $[+ 0]_{原} = 0, 0000000$ ， $[- 0]_{原} = 1, 0000000$
缺点：符号位不能参与运算，需要设计复杂的硬件电路才能处理

反码

反码：若符号位为 $0$ ，则反码与原码相同，若符号位为 $1$ ，则数值位全部取反。
反码只是由原码转换为补码的一个中间态，实际上并没有作用。

补码

补码：若符号位为 $0$ ，则反码与原码相同，若符号位为 $1$ ，则数值位全部取反再加一，即反码加一。
用补码表示，符号位可以参与运算，但补码的数值位不能解读为“位权”

移码

移码：补码的基础上符号位取反
移码=真值(补码表示) + 偏置值(通常为 $2^{n - 1}$ )。如：真值为-127的数补码为10000001，加上偏置值10000000即得对应-127的移码00000001
移码表示下的从最小到最大刚好对应无符号整数表示下的最小到最大
移码只能用于表示整数，可以很方便用硬件电路对比大小，故常用于浮点数的阶码

各种码对比

打开 PDF

正数：原码=反码=补码
负数
- 原码 $\Leftrightarrow$ 反码：符号位不变，数值位取反
- 对于负数的补码，最右边的1及其右边同原码，最右边的1左边同反码。 ^[提示：根据补码的定义，补码=反码+1，所以从右往左连续的 1 都因为进位而变为0，直到进位碰到第一个0为止，且这一位仍需要进1]
  - 反码 $\Rightarrow$ 补码：末位+1，即：从右往左找到第一个0，这个0及其右边所有的数值位按位取反
  - 补码 $\Rightarrow$ 反码：建议补码 $\Rightarrow$ 原码 $\Rightarrow$ 反码
  - 补码 $\Leftrightarrow$ 原码：从右往左找到第一个1，这个1左边所有的数值位按位取反

$n + 1$ bit	合法表示范围	最大的数	最小的数	真值0的表示
带符号：原码	$- (2^{n} - 1) ⩽ x ⩽ 2^{n} - 1$	$0, 111 \dots 111$	$1, 111 \dots 111$	$[+ 0]_{原} = [- 0]_{原} = 0, 000 \dots 000 1, 000 \dots 000$
带符号：反码	$- (2^{n} - 1) ⩽ x ⩽ 2^{n} - 1$	$0, 111 \dots 111$	$1, 000 \dots 000$	$[+ 0]_{反} = [- 0]_{反} = 0, 000 \dots 000 1, 111 \dots 111$
带符号：补码	$- 2^{n} ⩽ x ⩽ 2^{n} - 1$	$0, 111 \dots 111$	$1, 000 \dots 000$	$[0]_{补} = 0, 000 \dots 000$
带符号：移码	$- 2^{n} ⩽ x ⩽ 2^{n} - 1$	$1, 111 \dots 111$	$1, 000 \dots 000$	$[0]_{移} = 1, 000 \dots 000$
无符号整数	$0 ⩽ x ⩽ 2^{n + 1} - 1$	$1111 \dots 111$	$0000 \dots 000$	$0000 \dots 000$

判断溢出：手算做题可以带入十进制验证，是否超出合法范围

对照表

无符号数： $0 \sim 127$ , $128 \sim 255$

原码： $+ 0 \sim 127$ , $- 0 \sim - 127$

反码： $+ 0 \sim 127$ , $- 127 \sim - 0$ （负数的话原码数值位取反）

解决了原码一会儿变大，一会儿变小的问题

补码： $0 \sim 127$ , $- 128 \sim - 1$ （负数的话反码末尾+1，导致实际值-1）

解决了反码+0,-0的问题

移码： $- 128 \sim - 1$ , $0 \sim 127$ （补码符号位反）

让真值完全按序增加

| 行数 | 机器数 | 无符号数 | 原码 | 反码 | 补码 | 移码 |

|:----:|:--------:|:--------:|:----:|:----:|:-----:|:----:|

| 1 | 00000000 | 0 | +0 | +0 | +0,-0 | -128 |

| 2 | 00000001 | 1 | +1 | +1 | +1 | -127 |

| 3 | 00000010 | 2 | +2 | +2 | +2 | -126 |

| … | … | … | … | … | … | … |

| 126 | 01111101 | 125 | +125 | +125 | +125 | -3 |

| 127 | 01111110 | 126 | +126 | +126 | +126 | -2 |

| 128 | 01111111 | 127 | +127 | +127 | +127 | -1 |

| 129 | 10000000 | 128 | -0 | -127 | -128 | 0 |

| 130 | 10000001 | 129 | -1 | -126 | -127 | 1 |

| 131 | 10000010 | 130 | -2 | -125 | -126 | 2 |

| … | … | … | … | … | … | … |

| 253 | 11111100 | 252 | -124 | -3 | -4 | 124 |

| 254 | 11111101 | 253 | -125 | -2 | -3 | 125 |

| 255 | 11111110 | 254 | -126 | -1 | -2 | 126 |

| 256 | 11111111 | 255 | -127 | -0 | -1 | 127 |

2.1.3 定点小数的表示和运算

定点小数：最高一位是符号位， $0$ 是正， $1$ 是负，小数点位置隐含在符号位后面，是纯小数。

$n + 1$ bit	合法表示范围	最大的数	最小的数	真值0的表示
带符号：原码	$- (1 - 2^{- n}) ⩽ x ⩽ 1 - 2^{- n}$	$0.111 \dots 111$	$1.111 \dots 111$	$[+ 0]_{原} = [- 0]_{原} = 0.000 \dots 000 1.000 \dots 000$
带符号：反码	$- (1 - 2^{- n}) ⩽ x ⩽ 1 - 2^{- n}$	$0.111 \dots 111$	$1.000 \dots 000$	$[+ 0]_{反} = [- 0]_{反} = 0.000 \dots 000 1.111 \dots 111$
带符号：补码	$- 1 ⩽ x ⩽ 1 - 2^{- n}$	$0.111 \dots 111$	$1.000 \dots 000$	$[0]_{补} = 0.000 \dots 000$

定点小数vs定点整数

运算逻辑相同
位数扩展时不一样【注意】

2.2 运算方法和运算电路

2.2.0 奇偶校验码

奇偶校验原理：奇偶校验码= $1$ 位校验位+ $n$ 位有效信息位

奇校验：让整个校验码（有效信息位加上校验位）中为“1”的个数为奇数
偶校验：让整个校验码（有效信息位加上校验位）中为“1”的个数为偶数
- 偶校验的硬件实现
  - 求偶校验位：所有位进行异或运算，得到的结果即为偶校验位
  - 进行偶校验：所有位进行异或运算，若结果为1说明出错
- 异或（模2加）： $0 \oplus 0 = 0$ ， $0 \oplus 1 = 1$ ， $1 \oplus 0 = 1$ ， $1 \oplus 1 = 0$

注意：偶数个比特的错误无法被发现

2.2.1 基本运算部件

电路基础知识

逻辑门电路

逻辑门电路（数字电路基础补充）.pdf

最基本的逻辑运算

与 $Y = A \cdot B$ ：与门
或 $Y = A + B$ ：或门
非 $Y = \overline{A}$ ：非门

复合逻辑

与非 $Y = \overline{A \cdot B}$ ：与非门， $\overline{A \cdot B} = \overline{A} + \overline{B}$
或非 $Y = \overline{A + B}$ ：或非门， $\overline{A + B} = \overline{A} \cdot \overline{B}$
异或 $Y = A \oplus B$ ：异或门， $A \oplus B = \overline{A} \cdot B + A \cdot \overline{B}$
同或 $Y = A ⊙ B$ ：同或门， $A ⊙ B = \overline{A \oplus B}$

逻辑表达式就是电路的数学化表示。根据逻辑运算的规则对逻辑表达式进行优化，也就是在优化电路

多路选择器与三态门

多路选择器、三态门.pdf

多路选择器(multiplexer, MUX)：电路的“守门员”，根据控制信号的值，MUX在多个输入数据选择其中某一个进行输出，其他输入数据直接阻断
若有 $k$ 个输入，则控制信号的位数 $m ⩾ ⌈ lo g_{2} k ⌉$
有的多路选择器可能会预留一个控制信号，用于拦截所有的输入

多路选择器

三态门：电路的“守门员”，根据控制信号的值决定是否让输入的数据通过
三态门的控制信号通常只需要1bit

三态门

加法器.pdf

一位全加器(FA)

异或门实现一位加法

输入信号 $A_{i}, B_{i}, C_{i - 1}$
输出信号 $S_{i} = A_{i} \oplus B_{i} \oplus C_{i - 1}$
输出信号 $C_{i} = A_{i} B_{i} + (A_{i} \oplus B_{i}) C_{i - 1}$ ^[提示：当输入中至少有两个1时输出1，即：输出信号 $A_{i}$ 和 $B_{i}$ 同时为1，或者 $A_{i}$ 和 $B_{i}$ 有一个为1且 $C_{i - 1}$ 为1]

用一位全加器实现多位加法

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

1位全加器

并行加法器

即输入端允许并行输入 $n$ bit

串行进位加法器

即从进位方式上看进位信息串行产生

把 $n$ 个全加器串联起来，就可以进行两个 $n$ 位数的相加
串行进位的并行加法器：串行进位又称为行波进位，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的
缺点：进位信息串行产生，计算速度取决于进位产生和传递的速度。位数越多运算速度越慢

串行进位加法器

并行进位加法器

即从进位方式上看进位信息并行产生

并行进位加法器.pdf

如何更快地产生进位？

$C_{i} = A_{i} B_{i} + (A_{i} \oplus B_{i}) {A_{i - 1} B_{i - 1} + (A_{i - 1} \oplus B_{i - 1}) \dots [A_{1} B_{1} + (A_{1} \oplus B_{1}) C_{0}]}$

第 $i$ 位向更高位的进位 $C_{i}$ 可以根据被加数、加数的第 $1 \sim i$ 位再结合 $C_{0}$ 即可确定

记进位产生函数 $G_{i} = A_{i} B_{i}$ ，进位传递函数 $P_{i} = A_{i} \oplus B_{i}$ ，则 $C_{i} = G_{i} + P_{i} C_{i - 1}$
并行进位的并行加法器：各级进位信号同时形成，又称先行进位、同时进位
特点：所有进位信息都是同时产生的，几乎没有延迟，因此运算速度更快
随着加法器位数的增加，电路结构会变得很复杂，故通常采用4位并行加法器，即由4个FA和一些新的线路、运算逻辑组成

4位CLA部件

带标志位的加法器

在并行加法器的基础上，增加电路逻辑，输出标志位

标志位的生成

算术逻辑单元(ALU)

功能：算术运算（加减乘除等）、逻辑运算（与或非异或等）、辅助功能（移位求补等）
基本结构：输入、输出、控制

ALU

$A_{i}, B_{i}$ 为输入信号（操作数）
$F_{i}$ 为输出信号（运算结果）
$K_{i}$ 为控制信号（指令译码产生）
控制信号数量 $n$ 取决于ALU支持多少种运算， $n$ bit控制信号对应 $2^{n}$ 种运算（有时候也要考虑留一种状态来表示什么也不做）
ALU的宽度即ALU运算对象的宽度，通常与字长相同

2.2.2 定点数的移位运算

定点数的移位运算.pdf

移位：通过改变各个数码位和小数点的相对位置从而改变各个数码位的位权。可用移位运算实现乘法、除法
由于原、反、补码位数有限，因此有些时候移位操作并不能精确等效乘法、除法

算数移位

算数移位：符号位保持不变，仅对数值位移位。

原码
- 右移：高位补 $0$ ，低位舍弃。若舍弃的位 $= 0$ ，则相当于 $\div 2$ ；若舍弃的位 $\neq = 0$ ，则会丢失精度
- 左移：低位补 $0$ ，高位舍弃。若舍弃的位 $= 0$ ，则相当于 $\times 2$ ；若舍弃的位 $\neq = 0$ ，则会出现严重误差
反码
- 正数：同原码
- 负数：右移高位补 $1$ 低位舍弃，左移低位补 $1$ 高位舍弃
补码（补码的右边与原码相同，左边与反码相同）
- 正数：同原码
- 负数：右移（同反码）高位补 $1$ 低位舍弃；左移（同原码）低位补 $0$ 高位舍弃

逻辑移位

逻辑移位：可以看做对无符号数的算数移位

右移：高位补0，低位舍弃
左移：低位补0，高位舍弃

循环移位

考前记一记

不带进位位的循环移位：移出的位替换进位位，并补上空缺
带进位位的循环移位：移出的位放到进位位，原进位位补上空缺

循环移位

2.2.3 定点数的加减运算

不管是补码减法，还是无符号减法，都是用被减数加上减数对应负数的补码来实现的

算的时候为了效率或许可以直接使用十六进制计算

定点数的加减运算.pdf

补码的加减运算

补码的加法：从最低位开始，按位相加（符号位参与运算）并往更高位进位
补码的减法： $A - B = A + (- B)$
- $[B]_{补}$ <-> $[- B]_{补}$ ：全部位取反（包含符号位），末位+1
- 快速解法：右往左找到第一个1，这个1左边全部位按位取反 ^[提示：对于负数的补码，最右边的1及其右边同原码，最右边的1左边同反码。而 $B$ 与 $- B$ 的原码数值部分各位相同，反码各位全部相反。因此在补码中，这个1及其右边二者相同，这个1左边二者相反]

补码加减运算器

对于减法，将减数按位取反，并令进位信号Sub=1 ^[提示：进行减法运算时，需要将减数取反并+1。取反由非门实现，而+1就是加进位信号Sub] 考前记一记

无符号整数的加法/减法也可以用该电路实现，用法相同（判断溢出方式不同，无符号看CF，有符号看OF）

补码加减运算器

溢出判别方法

仅当两个符号相同的数相加或两个符号相反的数相减才可能产生溢出

补码定点数加减运算溢出判断的方法有3种：
- 采用单符号位：根据运算前后操作数的符号判断。参加操作的两个数符号相同，结果又与原操作数符号不同，则表示结果溢出
- 采用单符号位：根据数据位的进位情况判断。若符号位的进位和最高数据位的进位相同，则说明没有溢出，否则表示发生溢出
- 采用双符号位：最高位符号位代表永远正确的符号。运算结果的两个符号位相同，表示未溢出；两个符号位不同则表示溢出 ^[补充：双符号位补码也称模4补码，对应的单符号位补码也称模2补码]
乘法溢出的判别：结果保留 $n$ 位
- 手算判溢出：带入十进制计算乘法结果，判断该结果是否超出了 $n$ 位所能表示的范围。若超出则溢出
- 机器判溢出：
  - 无符号数乘法： $n$ 位 × $n$ 位，用 $2 n$ 位保存中间结果。仅当前 $n$ 位都是 0 时，才不溢出
  - 有符号补码乘法： $n$ 位 × $n$ 位，用 $2 n$ 位保存中间结果。仅当前 $n + 1$ 位全 0 或全 1 时，才不溢出

标志位的生成

除了得到相加结果外，还会输出4个标志位信息考前记一记

OF(Overflow Flag)溢出标志：用于判断带符号数加减运算是否溢出。溢出时为1，否则为0
- $O F = C_{n} \oplus C_{n - 1}$ ，即符号位产生的进位与最高有效数据位产生的进位进行异或
- OF位对无符号数的加减法无意义，无符号数看CF
SF(Sign Flag)符号标志：用于判断带符号数加减运算结果的正负性。结果为负时为 1，否则为0
- $S F = S_{n}$ ，即符号位的本位和
- SF位对无符号数的加减法无意义
ZF(Zero Flag)零标志：用于判断加减运算结果是否为0。结果为 0 时为1，否则为0
- $Z F = \overline{S_{1} + S_{2} + \dots + S_{n}}$ ，即运算结果中的 $n$ bit全部为 $0$
CF(Carry Flag)进位/借位标志：用于判断无符号数加减运算是否溢出。进位/借位时为 $1$ ，否则为 $0$
- $C F = 最高位产生的进位 \oplus s u b$ ，其中 sub 为加减控制信号，加法0减法1
- CF位对有符号数的加减法无意义，有符号数看OF

2.2.4 定点数的乘除运算

乘法运算的实现思想

原码一位乘法

原码的乘法运算.pdf

设机器字长为 $n + 1$ （ $n$ 个数值位）
实现方法
- 符号位单独处理：符号位 $= x_{s} \oplus y_{s}$
- 数值位通过被乘数和乘数绝对值的 $n$ 轮加法、移位完成
  1. 正式开始乘法之前，ACC置0
  2. MQ中最第低位为当前运算位。若当前运算位 $= 1$ ，则ACC加上被乘数；若当前运算位 $= 0$ ，则ACC加上 $0$
  3. 每轮加法后ACC、MQ的内容统一逻辑右移（ACC的最低位移动到了MQ的最高位位置；MQ之前的最低位被丢弃，更新当前运算位）
    
    计算过程可能会产生局部溢出，但这只是中间结果，运算完毕后还要进行逻辑右移操作，将进位位移入部分积的最高位考前记一记
  4. 乘数的符号位不需要参与运算

例：机器字长为5位（含1位符号位， $n = 4$ ）， $x = - 0.1101, y = + 0.1011$ ，采用原码一位乘法求 $x \cdot y$

原码乘法

具体过程如下：

原码乘法运算过程

符号位 $P_{s} = x_{s} \oplus y_{s} = 1 \oplus 0 = 1$ ，得： $x \cdot y = - 0.1001 1111$

补码一位乘法

又称Booth算法

打开 PDF

考前记一记

乘数采用单符号位，末位增设辅助位 $y_{n + 1}$ ，初值为 $0$ ；
采用 $y_{n + 1}$ 与 $y_{n}$ 的差值判断各步的具体运算：
- 差值为 $1$ 时，累加上 $[x]_{补}$ ；
- 差值为 $0$ 时，累加上 $0$ ；
- 差值为 $- 1$ 时，累加上 $[- x]_{补}$ ；
按照上述算法进行 $n + 1$ 次累加操作， $n$ 次算数右移操作即可完成乘积运算
补码乘法中，符号位参与运算，不需要单独计算符号位

补码乘法

辅助位由MQ多扩展一位而来，初始为0，每次右移会使MQ的最低位顶替原本的辅助位
ACC与X也随着MQ多增加一位，所有寄存器都统一用 $n + 2$ 位，采用双符号位补码运算
会有辅助电路实现 $[- x]_{补}$ 的转换

原码的一位乘法 vs 补码的一位乘法

原码：进行 $n$ 轮加法、移位

补码：需要在原码的基础上多来一次加法

原码：根据MQ中的最低位，每次加法可能 $+ 0$ （最低位=0）、 $+ [∣ x ∣]_{原}$ （最低位=1）

补码：根据MQ中的最低位和辅助位，每次加法可能 $+ 0$ （辅助位-最低位=0）、 $+ [x]_{补}$ （辅助位-最低位=1）、 $+ [- x]_{补}$ （辅助位-最低位=-1）

原码：每次移位是逻辑右移

补码：每次移位是算数右移

原码：符号位不参与运算

补码：符号位参与运算

例：机器字长为5位（含1位符号位， $n = 4$ ）， $x = - 0.1101, y = + 0.1011$ ，采用补码一位乘法求 $x \cdot y$

$[x]_{补} = 11.0011$ ， $[- x]_{补} = 00.1101$ ， $[y]_{补} = 00.1011$

原码除法

战术放弃

原码的除法运算.pdf

恢复余数法

商的符号和数值分开进行，减法操作用补码加法实现，商符由两个操作数的符号位“异或”形成。

符号位单独处理：符号位 $= x_{s} \oplus y_{s}$
数值位取绝对值进行除法运算
- 正式开始除法之前，MQ置 $0$
- 计算机默认上商 $1$ ，求得余数后根据余数正负来判断上商 $1$ 是否正确
  - 余数符号位为 $0$ ，上商 $1$
  - 余数符号位为 $1$ ，改为上商 $0$ ，并恢复余数
- 求余数：ACC=ACC $-$ 除数（ $+ [- ∣ y ∣]_{补}$ ）；恢复余数：ACC=ACC+除数（ $+ ∣ y ∣$ ）
- 每轮结束后，ACC、MQ的内容同一逻辑左移，ACC高位丢弃，MQ低位补 $0$
- 上商0/1，得到余数，余数末尾补 $0$

恢复余数法是一个循环过程：比较→上商（商为0时还需要恢复余数）→左移→比较→……，直到商达到规定的位数为止。一般商的位数与除数的位数相同

例：机器字长为5位（含1位符号位， $n = 4$ ）， $x = + 0.1011, y = + 0.1101$ ，采用原码恢复余数法求 $x / y$

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

不恢复余数法

不恢复余数法是对恢复余数法的改进，主要特点是：不够减的时候不需要恢复余数，而根据余数符号进行不同的运算处理。运算步数固定，控制简单，有效提高了除法的运算速度

个人理解：在恢复余数法中，当余数 $a$ 为负数时，需要加除数 $b$ ，得到结果 $a + b$ 后进行下一次运算，左移、减去除数，其结果为： $(a + b) \cdot 2 - b = 2 a + b$ ，因此等同于直接将余数左移然后加上除数

也称原码加减交替除法。商的符号和数值分开进行，减法操作用补码加法实现，商符由两个操作数的符号位“异或”形成。

先用被除数减去除数（ $∣ X ∣ - ∣ Y ∣ = ∣ X ∣ + [- ∣ Y ∣]_{补}$ ）：
若余数符号位为1，商0，并让余数左移1位再加上除数，得到新余数
若余数符号位为0，商1，并让余数左移1位再减去除数，得到新余数
最后一步中，如果余数为负，仍然需要商0并恢复余数

注意：对于定点小数的运算，需要保证结果同样为定点小数，即规定被除数小于除数，所以正常来讲第一步得到的符号位为1，即被除数 $-$ 除数为负数

例：机器字长为5位（含1位符号位， $n = 4$ ）， $x = + 0.1011, y = + 0.1101$ ，采用原码加减交替法求 $x / y$

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

原码加减交替法

$Q_{s} = x_{s} \oplus y_{s} = 0 \oplus 0 = 0$ ，得 $x / y = + 0.1101$ ，余 $0.0111 \times 2^{- 4}$

补码除法

战术放弃

补码的除法运算.pdf

补码除法：加减交替法

符号位参与运算
被除数/余数、除数采用双符号位
若被除数与除数同号，则被除数减去除数；若异号，则被除数加上除数
余数和除数同号，则商1，余数左移1位减去除数；

余数和除数异号，则商0，余数左移1位加上除数
最后一步中，最后一位商恒置为1，精度误差不超过 $2^{- n}$

例：机器字长为5位（含1位符号位， $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 \times 2^{- 4}$

2.2.5 C语言中的整数类型及类型转换

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

有符号与无符号整数转换，不改变二进制内容
长整数转换为短整数，高位截断，只保留低位
短整数转换为长整数，符号扩展，用符号位填充
无符号短整数转换为无符号长整数，零扩展，用0填充

void main(){
	short x=-4321;						//x=1110 1111 0001 1111
	unsigned short y=(unsigned short)x;	//y=1110 1111 0001 1111
	//有符号转换为无符号整数，不改变二进制内容，y=61215
 
	int a =165537, b=-34991;		//a=0x000286a1, b=0xffff7751
	short c=(short)a, d=(short)b;	//    c=0x86a1,     d=0x7751
	//长整数转换为短整数，高位截断，只保留低位，c=-31071,d=30545
 
	short x=-4321;	//x=0xef1f
	int m=x;	//m=0xffffef1f
	//短整数转换为长整数，符号扩展，用符号位填充
 
	unsigned short n=(unsigned short)x;	//n=0xef1f
	unsigned int p=n;				//n=0x0000ef1f
	//无符号短整数转换为无符号长整数，零扩展，用0填充
}

2.2.6 数据的存储及排列

数据的存储和排列.pdf

大小端存储

最高有效字节(MSB)，最低有效字节(LSB)
多字节数据在内存里一定是占连续的几个字节
大端模式：最高有效字节存储在低地址，最低有效字节存储在高地址（从高位到低位，便于人类阅读）
小端模式：最低有效字节存储在低地址，最高有效字节存储在高地址（从低位到高位，便于机器处理）

边界对齐

现代计算机通常是按字节编址，即每个字节对应1个地址，支持按字、半字、字节寻址
每次访存只能读/写1个字
假设存储字长为32位，则1个字=32bit，半字=16bit。则：字节地址=字地址左移两位=半字地址左移1位
边界对齐方式虽然浪费了一些存储空间，但可提高指令和取数的速度。对于机器字长为32位的计算机，数据以边界对齐方式存放，半字地址一定是2的整数倍，字地址一定是4的整数倍，这样无论所取的数据是字节、半字还是字，均可一次访存取出。所存储的数据不满足上述要求时，通过填充空白字节使其符合要求。
边界不对齐方式可以充分利用存储空间，但半字长或字长的指令可能会存储在两个存储字中，此时需要两次访存，并且对高低字节的位置进行调整、连接之后才能得到所要的指令或数据，从而影响了指令的执行效率
边界对齐方式相对边界不对齐方式是一种空间换时间的思想。

2.3 浮点数的表示与运算

2.3.1 浮点数的表示

浮点数的表示.pdf

浮点数的作用和基本原理

定点数的局限性：定点数表示的数字范围有限，但我们不能无限制地增加数据的长度
浮点数：在位数不变的情况下增加数据表示范围，可以类比科学记数法

浮点数的真值 $N = M \times r^{E}$ ，阶码的底 $r$ 通常为2，也可以取 $2^{i}$

尾数 $M$ ：数符 $S_{f}$ +尾数的数值部分，常用原码或补码表示的定点小数。尾数位数反映浮点数的精度
阶码 $E$ ：阶符 $J_{f}$ +阶码的数值部分，常用补码或移码表示的定点整数。阶码位数反映浮点数表示范围，阶码值反映小数点的实际位置
如果用8bit空间存储浮点数，阶码占3位，尾数占5位

浮点数的规格化

规格化操作：通过调整一个非规格化浮点数的尾数和阶码的大小，使非零的浮点数在尾数的最高数位上保证是一个有效值
- 左规：当浮点数运算的结果为非规格化时要进行规格化处理，将尾数算术左移一位，阶码 $- 1$ 。左规可能要进行多次
- 右规：当浮点数运算的结果尾数出现溢出时（双符号为为01或10），将尾数算术右移一位，阶码 $+ 1$ 。右规只需进行一次
与非规格化浮点数相比，采用规格化浮点数的目的是为了增加数据的表示精度，充分利用尾数有效位数

浮点数的表示范围

规格化浮点数的特点

用原码表示的尾数进行规格化（规格化的原码尾数，最高数值位一定是1）考前记一记
- 正数为 $0.1 X X \dots X$ 的形式，其最大值表示为 $0.11 \dots 1$ ，最小值表示为 $0.10 \dots 0$ ，即表示范围为 $1/2 ⩽ M ⩽ (1 - 2^{- n})$ ；（第1位数值位必须为1）
- 负数为 $1.1 X X \dots X$ 的形式，其最大值表示为 $1.10 \dots 0$ ，最小值表示为 $1.11 \dots 1$ ，即表示范围为 $- (1 - 2^{- n}) ⩽ M ⩽ - 1/2$ ；（第1位数值位必须为1）

用补码表示的尾数进行规格化（规格化的补码尾数，符号位与最高数值位一定相反）考前记一记
- 正数为 $0.1 X X \dots X$ 的形式，其最大值表示为 $0.11 \dots 1$ ，最小值表示为 $0.10 \dots 0$ ，即表示范围为 $1/2 ⩽ M ⩽ (1 - 2^{- n})$ （同原码）
- 负数为 $1.0 X X \dots X$ 的形式，其最大值表示为 $1.01 \dots 1$ ，最小值表示为 $1.00 \dots 0$ ，即表示范围为 $- 1 ⩽ M ⩽ - (1/2 + 2^{- n})$ ；（第1位数值位必须为0）
正负上溢报错异常，正负下溢视为0

IEEE754标准

读音：I triple E754

754.pdf

表示格式：阶码用移码表示，尾数用原码表示（尾数隐含最高位1，实际为 $1. M$ ，注意隐含应该是仅适用于IEEE754标准）
- 真值=移码 $-$ 偏移值（将移码当做无符号数来计算）
  - 也可直接对十进制数进行操作，如：移码中的 $11111110 = (254)_{10}$ 所表示的值是 $254 - 127 = (127)_{10}$
  - 令偏置值 $= 2^{n - 1} - 1$ ，此时移码中的 $255, 0, 1, \dots, 254$ 对应真值 $- 128, - 127, \dots, 127$ （注意这里不是标准移码）考前记一记

类型	数符	阶码	尾数数值	总位数	偏置值
短浮点数`float`	1	8	23	32	127(7FH)
长浮点数`double`	1	11	52	64	1023(3FFH)
临时浮点数`long double`	1	15	64	80	16383(3FFH)

IEEE754浮点数 $\Rightarrow$ 十进制数
- 规格化短浮点数真值为 $(- 1)^{s} \times 1. M \times 2^{E - 127}$
- 规格化长浮点数真值为 $(- 1)^{s} \times 1. M \times 2^{E - 1023}$
十进制数 $\Rightarrow$ IEEE754浮点数
- 将十进制数转换为二进制数的形式，再对二进制数转换为 $1. M \times 2^{E - 127}$ 的形式
对于8位阶码，阶码全 $0$ 与全 $1$ 用作特殊用途，所以其正常范围为 $- 126 \sim 127$ 考前记一记
- 单精度浮点数最小绝对值： $(1.0)_{2} \times 2^{- 126}$
- 单精度浮点数最大绝对值： $(1.11 \dots 11)_{2} \times 2^{127}$
非规格化数考前记一记
- 阶码E为全0且尾数M不全为0时，表示非规格化小数 $\pm (0. X X \dots X X)_{2} \times 2^{- 126}$
- 阶码E为全0且尾数M全为0时，表示真值 $\pm 0$
- 阶码E为全1且尾数M全为0时，表示无穷大 $\pm \infty$
- 阶码E为全1且尾数M不全为0时，表示非数值“NaN”(Not a Number，如非法运算的结果)

2.3.2 浮点数的加减运算

浮点数的加减运算.pdf

浮点数加减运算

阶码和尾数采用补码表示

浮点数加减运算步骤（类比十进制科学计数法）

转换格式：真值转为机器码（阶数尾数采用补码表示）
对阶
- 求阶差 $Δ E$ ，若 $Δ E \neq = 0$ 则需要进行对阶
- 对阶：阶数小的向大的对齐 ^[提示：计算机内部尾数是定点小数，即 $1. X X X X$ 的形式，阶数小的向大的对齐更利于操作]，尾数算术右移一位，阶码 $+ 1$ ，直到阶码相同
尾数加减：通常采用双符号位表示尾数，这样可以挽救尾数溢出
结果规格化
舍入：计算机内部的尾数位数长度有限
- “0”舍“1”入法：类似十进制中的四舍五入法，即在尾数右移时，被移去的最高数值位为0，则舍去；被舍去的最高数值位为1，则在尾数末尾+1。这样做可能会使尾数又溢出，此时需要再做一次右规
- 恒置“1”法：尾数右移时，不论丢掉的最高数值位是“1”还是“0”，都使右移后尾数末位置为“1”
- 截断法：直接截取所需位数，丢弃后面的所有位
判断溢出
- 阶码上溢：抛出异常（右规可能会导致阶码上溢）
- 阶码下溢：按机器 0 处理（左规可能会导致阶码下溢）

Example

例题：已知十进制数 $x = - \frac{5}{256}, y = + \frac{59}{1024}$ ，按机器补码运算规则计算 $x - y$ ，结果用二进制表示。浮点数的格式如下：阶符取2位，阶码取3位，数符取2位，尾数取9位

转换格式： $x = - 5 \times 2^{- 8} = - 101 \times 2^{- 8} = - 0.101 \times 2^{- 5} = - 0.101 \times 2^{- 101}$ ，则 $x = 11011, 11.011000000$ ； $y = + 59 \times 2^{- 10} = + 111011 \times 2^{- 10} = + 0.111011 \times 2^{- 4} = + 0.111011 \times 2^{- 100}$ ，则 $y = 11100, 00.111011000$

对阶：阶差 $[Δ E]_{补} = 11011 - 11100 = 11011 + 00100 = 11111$ ，即 $Δ E = - 1 < 0$ ，则 $x$ 向 $y$ 对阶，尾数右移一位，阶码加一。因此 $x = 11100, 11.101100000$

尾数加减： $- y = 11100, 11.000101000$ ， $x - y = x + (- y) = 11100, 10.110001000$ ，发生尾数溢出

结果规格化：尾数右移一位，阶码加一，即： $x - y = 11101, 11.011000100$

舍入：无需舍入

判断溢出：阶码双符号位相同，未溢出。结果真值为 $(- 0.1001111)_{2} \times 2^{- 3}$

IEEE754浮点数加减运算

阶码采用移码表示，尾数采用原码表示，且尾数最高位隐藏

浮点数与定点数间的强制类型转换

无损转换（32位机器为例）

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

有损转换（精度丢失）

int->float：需要舍入处理，可能会损失精度（float尾数的数值位有1+23位）
float, double->int：仅保留整数部分。可能会溢出，也可能会损失精度（如小数转整数）

类型	16位机器	32位机器	64位机器
`char`	8	8	8
`short`	16	16	16(15)
`int`	16	32	32(31)
`long`	32	32	64(63)
`long long`	64	64	64
`float`	16	32	32(23+1)
`double`	64	64	64(52+1)

我的 Obsidian 知识库

探索

第2章 数据的表示和运算

2.1 数据的表示和运算

2.1.1 进位计数制及其相互转换

进制

r 进制->十进制

十进制->r 进制

二进制<->八进制、十六进制

真值与机器数

2.1.2 BCD码

8421码

余3码

2421码

2.1.4 定点整数的表示

无符号整数的表示和运算

带符号整数的表示和运算

原码

反码

补码

移码

各种码对比

2.1.3 定点小数的表示和运算

2.2 运算方法和运算电路

2.2.0 奇偶校验码

2.2.1 基本运算部件

电路基础知识

逻辑门电路

多路选择器与三态门

一位全加器(FA)

并行加法器

串行进位加法器

并行进位加法器

带标志位的加法器

算术逻辑单元(ALU)

2.2.2 定点数的移位运算

算数移位

逻辑移位

循环移位

2.2.3 定点数的加减运算

补码的加减运算

补码加减运算器

溢出判别方法

标志位的生成

2.2.4 定点数的乘除运算

原码一位乘法

补码一位乘法

原码除法

恢复余数法

不恢复余数法

补码除法

2.2.5 C语言中的整数类型及类型转换

2.2.6 数据的存储及排列

大小端存储

边界对齐

2.3 浮点数的表示与运算

2.3.1 浮点数的表示

浮点数的作用和基本原理

浮点数的规格化

浮点数的表示范围

IEEE754标准

2.3.2 浮点数的加减运算

浮点数加减运算

IEEE754浮点数加减运算

浮点数与定点数间的强制类型转换

关系图谱

目录

反向链接

第2章数据的表示和运算

$r$ 进制->十进制

十进制-> $r$ 进制