数制和编码

为什么计算机使用二进制编码

1. 二进制只有两种状态，元件制造成本低；
2. 1 和 0 刚好提供了逻辑值“真”和“假”，方便实现逻辑运算；
3. 编码和运算规则简单，方便通过逻辑门电路来实现。

进制转换

进位计数法

常见的进位计数法有十进制、二进制、八进制、十六进制等，一般逢 $10/2/8/16$ 就进一位，这里的 $10/2/8/16$ 被称为基数。

一般来说，二进制转换到八进制或十六进制比较简单，因为 $8$、$16$ 都是 $2$ 的倍数，只需要将二进制每三/四位分为一组，再将每组转换为对应进制的数即可。

对于其他进制而言，可以先将其转换为 $10$ 进制，再进行转换。

将整数从十进制转换到任意进制需要用到 除基取余法 ，即除以要转换进制的基数，得到余数，并对商再次进行同样的操作，直到商为 $0$，最后将余数按照 从下到上 的顺序排列即可，如求 $23$ 的二进制：

$$\begin{align*} 23 \div 2 &= 11 \cdots 1 \\ 11 \div 2 &= 5 \cdots 1\\ 5 \div 2 &= 2\ \cdots 1\\ 2 \div 2 &= 1\ \cdots 0 \\ 1 \div 2 &= 0\ \cdots 1 \ \end{align*}$$

可以得到其二进制数为 $10111$.

对于小数，需要使用 乘基取整法，即乘以基数，取其整数部分，直到乘积为 $1.0$ 或精度符合要求之后结束，最后按照 从上到下 的顺序排列。

warning

$N$ 位 $10$ 进制和 $2$ 进制数分别能表示 $10^N,2^N$ 个数字，这也是计算机运算存在误差的原因，它表示仅有 $0.2^N$ 的概率十进制数可以用二进制表示。

BCD 码

二进制编码的十进制数（$Binary-Coded Decimal,\ BCD$），采用 $4$ 位二进制数来表示 $1$ 位十进制数（$2^4=16>10$），此法可以使得二进制和十进制转换得以快速进行，但是有冗余状态。

常用 $BCD$ 码：

1. $8421$ 码，有权码，即 $D=8b_{3}+4b_{2}+2b_{1}+1b_{0}$ ，若两个 $8421$ 码相加小于等于 $9$ ，则不需要修正，若大于 $9$ ，则需要加 $6$ 修正，因为落在这个区间内为无效码。
2. 余 $3$ 码：无权码，在 $8421$ 码的基础上加 $(0011)_{2}$ 形成的，因此每个数都多余 $3$，这样相加就不需要修正了。
3. $2421$ 码，有权码，即 $D=2b_{3}+4b_{2}+2b_{1}+1b_{0}$ ，特点是大于等于 $5$ 的 $4$ 位二进制数中最高位为 $1$，小于 $5$ 的最高位为 $0$.

ASCLL 码

$ASCII$ 码使用指定的 $7$ 位或 $8$ 位二进制数组合来表示 $128$ 或 $256$ 种可能的字符。标准 $ASCII$ 码也叫基础 $ASCII$ 码，使用 $7$ 位二进制数（剩下的 $1$ 位二进制为 $0$）来表示所有的大写和小写字母，数字 $0$ 到 $9$、标点符号，以及在美式英语中使用的特殊控制字符。其中：$0\sim31$ 及 $127$ (共 $33$ 个) 是控制字符或通信专用字符，这些字符不可以显示。

常用的符号 $ASCLL$ 码如下

符号	编码
空格	20H
1	31 H
A	41 H
a	61 H

汉字编码

区位码：使用两个字节表示一个汉字，每个字节使用七位编码，将汉字和符号排列在一个表中，两个字节分别表示横纵坐标；

国标码：区位码的十六进制加上 $2020H$，这是为了兼容不支持汉字的机器，防止被转换为 $ASCLL$ 中的控制字符；

汉字内码：国标码的十六进制加上 $8080H$，直接跳过 $ASCLL$ 的范围。

汉字的内码有:

1. GB2312-1980
2. GBK
3. GB18030-2000
4. ISO/IEC10646-1、Unicode 2.0

定点数的编码表示

根据小数点的位置是否固定，计算机中有两种数据格式：定点表示和浮点表示。

常用定点补码整数表示整数，定点原码小数表示浮点数的尾数部分，移码表示浮点数的阶码部分。

定点整数和定点小数没啥好说的，第一位是符号位，其他是数值位，但是注意小数转换为补码时，最后的 $0$ 不需要变为 $1$，如 $-0.110101\mid000$ 应该先对最后一个 $1$ 以前的数取反 $1.001010 \mid000$，即最后的 $000$ 不变，再加一得到 $1.001011\mid 000$.

caution

定点整数/小数都是纯整数/小数，即只有整数/小数部分。

表示方法主要有 4 种：原码、补码、反码和移码。

原码：原码首位表示正负，其他位表示数值绝对值大小。

补码：原码的加减比较复杂，因此提出了补码来方便计算。 方式为 除了符号位按位取反再加 1，要求负数的原码只需要再次求补即可。

变形补码：又称 模4补码 ，即用两个二进制位来表示数字的符号位，其余与补码相同，用 $00$ 表示正，用 $11$ 表示负，用变形补码进行加减运算时，当运算结果的符号位出现 $01/10$ ，则表示产生正/负溢。

caution

原码有两个 $0$，正零（$0000$）和负零（$1000$）；补码只有一个 $0$（$0000$），补码（$1000$）表示的是 $-1000$，即 $-8$；可以认为，在补码中，原来的负零被分配到表示最小的数去了。

反码：负数则数值位取反即可。

移码：移码常用来表示浮点数的阶数，且 只能用来表示整数。 移码就是真值加了一个常数 $Y=X+2^n, -2^n\leq X<2^n$，其中机器字节长为 $n$，其和补码 符号位相反。

info

负数的反码/补码的数值部分越大/小，绝对值越小/大，真值越大/小，越靠近/远离 $0$.

运算方法和运算电路

基本运算部件

计算机中运算器由 $ALU$、移位器、状态寄存器和通用寄存器组成。 $ALU$ 的核心是加法器。

一位全加器

全加器（$FA$）是最基本的加法单元，输入为两个加数和低位传来的进位，输出为一个结果和进位。

和表达式为 $S=A\oplus B\oplus C$，进位表达式为 $C=AB+(A\oplus B)C$

串行进位加法器

将一些全加器串联可以得到串行进位加法器，每一级的进位依赖于前一级的输出，因此整个计算过程是串行的，严重影响计算时间。

并行进位加法器

进位计算公式为

$$C_{i}=G_{i}+P_{i}C_{i-1}$$

info

其中 $G_{i}=A_{i}B_{i}\ \ \ P_{i}=A_{i}\oplus B_{i}$，分别表示生成（$generate$）和传递（$propagate$），生成表示是否要产生进位，传递表示是否要将低位的进位传递给高位。若两个加数都为 $1$ 时，会产生进位；若存在加数为 $1$，低位进位为 $1$ ，则也会产生进位。

以四位加法距离，进位公式为

$$\begin{align*} C_{1}&=G_{1}+P_{1}C_{0} \\ C_{2}&=G_{2}+P_{2}G_{1} + P_{2}P_{1}C_{0} \\ C_{3}&=G_{3}+P_{3}G_{2} + P_{3}P_{2}G_{1}+P_{3}P_{2}P_{1}C_{0} \\ C_{4}&=G_{4}+P_{4}G_{3} + P_{4}P_{3}G_{2}+P_{4}P_{3}P_{2}C_{1}+P_{4}P_{3}P_{2}P_{1}C_{0} \end{align*}$$

当位数太多时，电路会过于复杂，因此实际可以四位为一组，组内使用并行进位加法器，组间使用串行进位加法器或并行进位加法器（两级（多级）先行进位加法器）。

带标志加法器

可以用于带符号整数的加减运算，需要额外处理标志位信息。

溢出标志 $OF=C_{n}\oplus C_{n-1}$，符号标志为和的符号，零标志位 $ZF=1$ 当且仅当 $F=0$，进位/借位标志 $CF=C_{out}\oplus C_{in}$.

算术逻辑单元（ALU）

info

$ALU$ 可以实现加减乘除、与或非、移位等操作，$ALU$ 的核心是带标志加法器。

$ALU$ 接收两个 $n$ 位操作数，一个进位，和一个操作控制 $ALUop$，用于控制计算类型。

定点数移位运算

就是将数值整体左移或右移，超出的位数直接舍弃，并在空出的位置上添 $0$ 或 $1$，循环移位就将超出的部分移动到空出的部分上。

算术移位

算术移位的对象是有 符号数，移位过程中符号保持不变；左移表示乘二，右移表示除以二；

对于正数而言，原码、补码、反码的移位都是添 $0$；

对于负数，原码仍旧是添 $0$，反码添 $1$，补码左移添 $0$，右移添 $1$.

逻辑移位

即无视符号位，直接移动。

循环移位

循环移位分为 带进位标志位的循环移位（大循环） 和 不带进位标志为的循环移位（小循环），大循环就是进位标志位一起参与移位。

定点数的加减运算

补码加减运算规则

加法：补码直接相加，舍去高位。

减法：减数求负补码，转换为加法。

补码加减运算电路

要实现减法，需要在加法器的输入前加 $n-1$ 位反向器进行取反，并使用一个二选一多路选择器控制，当信号 $sub$ 为 $1$ 时，则认为做减法，二选一多路选择器选择取反的数据。 同时信号 $sub$ 一直作为进位传送给加法器，若是减法则起到取反之后加一的作用。

输出运算结果和标志位，零标志 $ZF=1$ 表示结果为 $0$；溢出标志 $OF$ 对于有符号数表示溢出，对于无符号数无意义；符号标志 $SF$ 表示结果正负，对于无符号数无意义；进/借位标志 $CF$ 表示 无符号整数 的进位和借位，判断是否有溢出，做加法时，$CF=1$ 表示产生进位，有溢出，实际输出不变，做减法时，$CF=1$ 表示产生借位，有溢出，实际输出取反。

判别溢出

一位符号位

$$V=A_{s}B_{s}\overline S+\overline{A_{s}B_{s}}S$$

根据输入的符号位和结果的符号为进行判断，$V=1$ 则表示溢出。

也可以根据数据位的进位情况进行判断

若符号位的进位和最高位的进位相同，则无溢出

$$V=C_{s}\oplus C_{1}$$

双符号位

基于这样的一个事实：若两个 $n$ 位数字相加，则用 $n+1$ 位来表示则一定不会溢出。 若两位符号相同，则无溢出，若为 $01$，则为正溢，$10$，则为负溢。

进位判别法

最高位向符号位的进位 $C_{n-1}$ 和符号位向更高位的进位 $C_{n}$，若不同，则发生溢出，可以表示为 $VF=C_{n-1}\oplus C_{n}$.

定点数的乘除运算

乘法运算由累加和右移操作实现，可以分为原码一位乘法和补码一位乘法。

原码一位乘法

符号和数值分开求，符号运算使用异或 $x_{s}\oplus y_{s}$，每次判断乘数的最后一位，如果为 $1$，则加上被乘数，否则不加，再右移一位；循环直到移动了 $n$ 位，$n$ 为乘数的位数。

补码一位乘法

如何根据补码快速求出其十进制

一个简单的方式是将最高位对应的十进制数值当作负数，其余位数的 $1$ 当作正数，相加即可，如 1101，其原码是 1011，对应十进制是 $-3$，直接通过补码计算为 $-8+4+1=-3$.

该原理基于补码的定义，因此可以推出负数补码的一般式，即最高为负数；再通过裂项，得到与最后两位的关系，这就是 booth 算法；通过该关系可以得到四种情况：

次低位	最低位	操作
0	0	+0，右移一位
0	1	+ [x] 补，右移一位
1	0	+[-x] 补，右移一位
1	1	+0，右移一位

一些细节如下：

1. 乘数被乘数和运算结果都是补码；
2. 部分积和被乘数 $x$ 使用双符号位，乘数 $y$ 使用单符号；
3. 初始部分积为 $0$，并且需要在 $y$ 的末尾添加一个最低位 $0$；
4. 累加 $n+1$ 次，右移 $n$ 次，$n$ 为 $y$ 的初始长度。

恢复余数法和加减法

太麻烦了，略。

数据存储和排列

大端方式：高位在前面

小端方式：低位在前面

数据以边界对齐的方式存储，如 32 位计算机，字地址一定是 4 的整数倍，若所存储数据不符合要求，会通过填充空白字节进行存储，可以提高读取指令和取数的速度。

浮点数的表示和运算

浮点数指小数点的位置可以浮动，这样在位数有限的情况下，扩大了数的表示范围，又保持了数的精度。

浮点数格式为

$$N=(-1)^S \times M R^E$$

其中 $S$ 用于控制正负；$M$ 为一个二进制定点小数，称为尾数，一般使用原码表示；$E$ 是一个二进制定点整数，称为 阶码或指数 ，$R$ 是基数，可以 约定 为 $2,4,16$ 等，现在一般是 $2$.

info

尾数反应浮点数的精度，阶码反应浮点数的表示范围。

溢出

运算结果大于最大正数被称为正上溢，小于最小正数被称为负上溢，在 0 到最小正数之间被称为正下溢，在 0 到最大负数之间被称为负下溢。

note

由于 754 可以使用非规格化尾数来表示浮点数，因此其表示下界更大，这可以看作是一种 渐进下溢；再下溢可以当 0 处理。

规格化

规格化的目的是为了充分利用尾数，使得有效数字能尽量占满尾数。 将尾数左/右移以达到尾数的最高位是有效数字的过程被称为左/右规。

info

规格化后的尾数大小应该满足 $\frac{1}{R}\leq M<1$.

caution

基数不同，尾数规格化的形式也不同，如基数为 $4$，则最高 $2$ 位不同时为 $0$.

IEEE 754 标准

32 位：$1$ 位符号、$8$ 位阶码、$23$ 位尾数，阶码偏置值为 $127$.

64 位：$1$ 位符号、$11$ 位阶码、$52$ 位尾数。阶码偏置值为 $1023$.

临时浮点数：$1$ 位符号、$15$ 位阶码、$64$ 位尾数，总计 $80$ 位。 阶码偏置值为 $16383$.

warning

这里的移码并不符合一般一般移码的性质，一般移码的偏置值计算是 $2^{n-1}$，而 $IEEE\ 754$ 中的阶码偏置值需要再减去 $1$: $2^{n-1} - 1$，这样 $0000\cdots(128)$ 和 $111\cdots(-127)$ 就可以被空出来表示其他作用了 （这段可能有问题），因此其移码的实际范围是 $-2^{n-1}+2\sim 2^{n-1}-1$，如 $-126\sim 127$.

若尾数为 $0$，当阶码全为 $0$ 时表示正/负零，全为 $1$ 表示正/负无穷；若尾数不为 $0$，而阶码全为 $1$，表示 $NaN$，为 $0$ 表示没有隐藏 $1$，是非规格化数。

隐含基数为 $2$.

对于规格化后的尾数，最高位总是 $1$ （若尾数使用补码表示，则需要分类讨论，若为负数，则最高位应该为 $0$，可以将逻辑化简为：符号位应该和最高位不同），因此将其再左移一位，可以将其隐藏，称为隐藏位，因此尾数实际有效位数会加 $1$.

bf16 和 tf32

浮点数 $fp 16$ 有 $5$ 位阶码和 $10$ 位尾数，在深度学习领域经常会因为范围不够导致溢出，因此引入了 $bf16$ 用于表示更大的范围，其拥有 $8$ 位阶码和 $7$ 位尾数，并且其表示范围和 $fp 32$ 对齐，因此可以进行混合精度训练；

此外还有 $tf 32$，其范围也和 $fp 32$ 对齐，使用相同的 $8$ 位阶数，保持范围不变，而尾数则使用和 $fp 16$ 相同的 $10$ 位，可以良好的兼容二者，并且提高速度。

加减运算

大致分为一下几个步骤：

1. 对阶，使阶数相同，阶数小的尾数右移
2. 尾数求和
3. 规格化，这里的规格化需要加上隐藏位
4. 舍入，对阶的过程中，将右移的尾数多保留两位，参与求和过程，最后对结果进行舍入
5. 溢出判断

info

舍入的常见方法有：

1. $0$ 舍 $1$ 入法：保留的最高位为 $1$ 则在尾数加 $1$，可能会需要再做一次右规。 若为 $0$ 则舍去；
2. 恒置 $1$ 法：将右移后的尾数末尾置 $1$；
3. 截断法：直接截取需要的位数；
4. 就近舍入：舍入到最接近的可表示值，如果有两个最接近的值，则舍入偶数；
5. 向正/负无穷方向舍入。

浮点数在数轴上的分布

整数在数轴上是均匀分布的，但是浮点数的表示范围和阶码有关，而尾数表示的是精度，假设对于四位的尾数，则对于每一个阶码的取值，只有 $2^3=8$ 种情况（第一位一定是 $1$），也即：

1. 在 $\frac{1}{2^n}\sim \frac{1}{2^{n-1}}$ 之间有 $8$ 个数字。 . .
2. 在 $\frac{1}{2}\sim 1$ 之间有 $8$ 个数字。 . .
3. 在 $2^{n-1}\sim 2^n$ 之间有 $8$ 个数字。 . .

可以观察到，距离原点越近的位置数字越多，分布越集中，精度越高，但是在 $2$ 的整数幂之间分布是均匀的。

浮点数的表示范围

要求浮点数的表示范围，可以分为几个部分，一个是尾数所表示的范围，一个是阶码表示的范围，再配上符号即可。

以一个 $16$ 位的浮点数为例，其中阶码长度 $6$，尾数长度 $9$，符号位 $1$.

尾数的范围

warning

以下情况不包括隐藏位。

	补码	原码	说明
最大正尾数	$0.111111111=1-2^{-9}$	$0.111111111=1-2^{-9}$	全是 $1$ 的情况
最小正尾数	$0.100000000=2^{-1}$	$0.100000000=2^{-1}$	根据尾数的性质，必须大于等于 $\frac{1}{2}$
最大负尾数	$1.111111111=-0.100000001=-(2^{-1}+2^{-9})$	$-0.100000000=-2^{-1}$	补码的尾数取不到 $-\frac{1}{2}$ 是因为 $-0.1\cdots$ 的补码是 $1.10\cdots$，不满足符号位和最高位不同的要求
最小负尾数	$1.000000000=-1$	$-0.111111111=-(1-2^{-9})$

info

对于有效数字位为 $n$ 位的定点小数（纯小数），若其全是 $1$，形如 $0.11111\cdots$，则其对应的十进制为 $1-2^{-n}$，因为这个数再加上 $0.000\cdots1$ 就会变成 $1$ .

阶码的范围

若根据 754 标准，阶码的偏移值是 $2^{6-1}-1=31$，而 $6$ 位无符号定点整数表示的范围是 $0\sim 63$，则阶码的范围是 $-31\sim 32$（真值减去偏移值）；而这里未作说明，因此可以使用 $-32\sim 31$

表示范围

	补码	原码
最大正数	$(1-2^9)\times 2^{31}$	$(1-2^9)\times 2^{31}$
最小正数	$2^{-1}\times 2^{-32}$	$2^{-1}\times 2^{-32}$
最大负数	$-(2^{-1}+2^{-9})\times 2^{-32}$	$-2^{-1}\times 2^{-32}$
最小负数	$-2^{31}$	$-(1-2^{-9})\times 2^{31}$

C 语言中的类型转换

这里只讨论隐式的类型转换，转换的基本原则是低精度类型向高精度类型转换，在运算过程中，有如下规则：

1. 参与运算类型不同，则先转换为同一类型；
2. 所有浮点运算都是以双精度计算，即使表达式只包含单精度，也会进行转换；
3. $char$ 和 $short$ 类型参与计算必须先转换为 $int$；
4. 赋值运算中会强制转换为左变量的类型。

在不同的系统中，C 语言中数据类型的长度是不同的 （单位：字节，一字节是四比特/位）：

数据类型	32 位系统	64 位系统
short	2	2
int	4	4
long	4	8
long long	8	8

一些常用整数 （补码）的表示范围：

1. int8 和 int16 的范围分别是 $-128\sim 127$ 和 $-32768\sim32767$；
2. uint8 和 uint16 的范围分别是 $0\sim 255$ 和 $0\sim 65535$.

数据检错和纠错

见计算机网络数据链路层。

总结和常见问题

浮点数阶码使用移码有什么好处

1. 比较大小更方便
2. 检验特殊值（$0$ 和无穷）方便

浮点数如何舍入

舍入的原则是使得误差范围对称，平均误差为 0，防止误差累积。并且方法要简单，速度快。 $IEEE \ 754$ 有 $4$ 种舍入方法。

1. 就近舍入，舍入为最近可以表示的数，若结果在两个可表示数中间，则选偶数
2. 正向舍入，向正无穷方向舍入
3. 负向舍入，向负无穷方向舍入
4. 截去，向 $0$ 方向舍入

现代计算机原码加减运算怎么实现

$IEEE\ 754$ 中，浮点数加减涉及到原码的运算，有两种方法

1. 转换为补码运算后再转换回来
2. 直接使用原码计算，符号和数值分开计算