数据的表示和运算

数制与编码

在计算机系统内部，所有的信息都是用二进制进行编码的，这样做的原因有以下几点：

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

进位计数法

进位计数法是一种计数的方法。常用的进位计数法有十进制、二进制、八进制、十六进制等。十进制数是日常生活中最常使用的，而计算机中通常使用二进制数、八进制数和十六进制数。

在进位计数法中，每个数位所用到的不同数码的个数称为基数。十进制的基数为 10（0 ~ 9），每个数位计满 10 就向高位进位，即“逢十进一”。十进制数 101，其个位的 1 显然与百位的 1 所表示的数值是不同的。每个数码所表示的数值等于该数码本身乘以一个与它所在数位有关的常数，这个常数称为位权。一个进位数的数值大小就是它的各位数码按权相加。

一个 $r$ 进制数（$K_{n} K_{n-1} \cdots K_{0} K_{-1} \cdots K_{-m}$）的数值可表示为：$$K_{n} r^{n} + K_{n-1} r^{n-1} + \cdots + K_{0} r^{0} + K_{-1} r^{-1} + \cdots + K_{-m} r^{-m} = \sum_{i=n}^{-m} K_{i} r^{i}$$式中，$r$ 是基数；$r^{i}$ 是第 $i$ 位的位权（整数位最低规定为第 0 位）；$K_{i}$ 的取值可以是 $0,1,\cdots,r-1$ 共 $r$ 个数码中的任意一个。

二进制。计算机中用得最多的是基数为 2 的计数制，即二进制。二进制只有 0 和 1 两种数字符号，计数“逢二进一”。它的任意数位的权为 $2^{i}$，$i$ 为所在位数。
八进制。八进制作为二进制的一种书写形式，其基数为 8，有 0 ~ 7 共 8 个不同的数字符号，计数“逢八进一”。因为 $r=8=2^{3}$，所以只要把二进制中的 3 位数码编为一组就是一位八进制数码，两者之间的转换极为方便。
十六进制。十六进制也是二进制的一种常用书写形式，其基数为 16，“逢十六进一”。每个数位可取 0 ~ 9、A、B、C、D、E、F 中的任意一个，其中 A、B、C、D、E、F 分别表示 10 ~ 15。因为 $r=16=2^{4}$，因此 4 位二进制数码与 1 位十六进制数码相对应。

不同进制数之间的相互转换

（1）二进制数转为八进制数和十六进制数

对于一个二进制混合数（既包含整数部分，又包含小数部分），在转换时应以小数点为界。

其整数部分，从小数点开始往左数，将一串二进制数分为 3 位（八进制）一组或 4 位（十六进制）一组，在数的最左边可根据需要加“0”补齐；
对于小数部分，从小数点开始往右数，也将一串二进制数分为 3 位一组或 4 位一组，在数的最右边也可根据需要加“0”补齐。最终使总的位数为 3 或 4 的整数倍，然后分别用对应的八进制数或十六进制数取代。

同样，由八进制数或十六进制数转换成二进制数，只需将每位改为 3 位或 4 位二进制数即可（必要时去掉整数最高位或小数最低位的 0）。

八进制数和十六进制数之间的转换也能方便地实现，十六进数制转换为八进制数（或八进制数转换为十六进制数）时，先将十六进制（八进制）数转换为二进制数，然后由二进制数转换为八进制（十六进制）数较为方便。

（2）任意进制数转换为十进制数

将任意进制数的各位数码与它们的权值相乘，再把乘积相加，就得到了一个十进制数。这种方法称为按权展开相加法。

（3）十进制数转换为任意进制数

一个十进制数转换为任意进制数，常采用基数乘除法。这种转换方法对十进制数的整数部分和小数部分将分别进行处理，对整数部分用除基取余法，对小数部分用乘基取整法，最后将整数部分与小数部分的转换结果拼接起来。

除基取余法（整数部分的转换）：整数部分除基取余，最先取得的余数为数的最低位，最后取得的余数为数的最高位（即除基取余，先余为低，后余为高），商为 0 时结束。
乘基取整法（小数部分的转换）：小数部分乘基取整，最先取得的整数为数的最高位，最后取得的整数为数的最低位（即乘基取整，先整为高，后整为低），乘积为 1.0 （或满足精度要求）时结束。

例如将十进制数 123.6875 转换成二进制数：

十进制数转换为任意进制数

因此整数部分 123 = (1111011)₂ ，小数部分 0.6885 = (0.1011)₂ ，所以 123.6875 = (1111011.1011)₂

注意：在计算机中，小数和整数不一样，整数可以连续表示，但小数是离散的，所以并不是每个十进制小数都可以准确地用二进制表示。例如 0.3，无论经过多少次乘二取整转换都无法得到精确的结果。但任意一个二进制小数都可以用十进制小数表示。

真值和机器数

在日常生活中，通常用正号、负号来分别表示正数（正号可省略）和负数，如 +15、-8 等。这种带“+”或“-”符号的数称为真值。真值是机器数所代表的实际值。

在计算机中，通常采用数的符号和数值一起编码的方法来表示数据。常用的有原码、补码和反码表示法。这几种表示法都将数据的符号数字化，通常用“0”表示“正”，用“1”表示“负”。如 0,101 （这里的逗号“,”实际上并不存在，仅为区分符号位与数值位）表示 +5。这种把符号“数字化”的数称为机器数。

BCD 码

二进制编码的十进制数（Binary-Coded Decimal, BCD）通常采用 4 位二进制数来表示一位十进制数中的 0 ~ 9 这 10 个数码。这种编码方法使二进制数和十进制数之间的转换得以快速进行。但 4 位二进制数可以组合出 16 种代码，因此必有 6 种状态为冗余状态。

下面列举几种常用的 BCD 码：

8421 码（最常用）。它是一种有权码，设其各位的数值为 $b_{3}$，$b_{2}$，$b_{2}$，$b_{0}$，则权值从高到低依次为 8，4，2，1，它表示的十进制数为 $D= 8b_{3} +4b_{2} + 2b_{1}+ 1b_{0}$。如 8 → 1000；9 → 1001。若两个 8421 码相加之和小于等于 (1001)₂ 即 (9)₁₀，则不需要修正；若相加之和大于等于 (1010)₂ 即 (10)₁₀，则要加 6 修正（从 1010 到 1111 这 6 个为无效码，当运算结果落于这个区间时，需要将运算结果加上 6），并向高位进位，进位可以在首次相加或修正时产生。
余 3 码。这是一种无权码，是在 8421 码的基础上加 (0011)₂ 形成的，因每个数都多余“3”，因此称为余 3 码。如 8 → 1011；9 → 1100。
2421 码。这也是一种有权码，权值由高到低分别为 2，4，2，1，特点是大于等于 5 的 4 位二进制数中最高位为 1，小于 5 的最高位为 0。如 5 → 1011 而非 0101。

字符与字符串

由于计算机内部只能识别和处理二进制代码，所以字符都必须按照一定的规则用一组二进制编码来表示。

（1）字符编码 ASCII 码

目前，国际上普遍采用的一种字符系统是 7 位二进制编码的 ASCII 码，它可表示 10 个十进制数码、52 个英文大写字母和小写字母（A ~ Z, a ~ z）及一定数量的专用符号（如 $、%、+、= 等），共 128 个字符。

在 ASCII 码中，编码值 0 ~ 31 为控制字符，用于通信控制或设备的功能控制；编码值 127 是 DEL 码；编码值 32 是空格 SP；编码值 32 ~ 126 共 95 个字符称为可印刷字符。

提示: 0 ~ 9 的 ASCII 码值为 48 (011 0000) ~ 57 (011 1001)，即去掉高 3 位，只保留低 4 位，正好是二进制形式的 0 ~ 9。

（2）汉字的表示和编码

在 1981 年的国家标准 GB 2312——1980 中，每个编码用两字节表示，收录了一级汉字 3755 个、二级汉字 3008 个、各种符号 682 个，共计 7445 个。

目前最新的汉字编码是 2000 年公布的国家标准 GB 18030，它收录了 27484 个汉字。编码标准采用 1 B、2 B 和 4 B。

汉字的编码包括汉字的输入编码、汉字内码、汉字字形码三种，它们是计算机中用于输入、内部处理和输出三种用途的编码。区位码是国家标准局于 1981 年颁布的标准，它用两字节表示一个汉字，每字节用七位码，并将汉字和图形符号排列在一个 94 行 94 列的二维代码表中。区位码是 4 位十进制数，前 2 位是区码，后 2 位是位码，所以称为区位码。

国标码将十进制的区位码转换为十六进制数后，再在每字节上加上 20 H。国标码两字节的最高位都是 0，ASCII 码的最高位也是 0。为了方便计算机区分中文字符和英文字符，将国标码两字节的最高位都改为“1”，这就是汉字内码。

区位码和国标码都是输入码，它们和汉字内码的关系（十六进制）如下:

国标码 = (区位码)₁₆ + 2020H
汉字内码 = (国标码)₁₆ + 8080H

校验码

校验码是指能够发现或能够自动纠正错误的数据编码，也称检错纠错编码。校验码的原理是通过增加一些冗余码，来检验或纠错编码。

通常某种编码都由许多码字构成，任意两个合法码字之间最少变化的二进制位数，称为数据校验码的码距。对于码距不小于 2 的数据校验码，开始具有检错的能力。码距越大，检错、纠错的能力就越强，而且检错能力总是大于等于纠错能力。

奇偶校验码

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

奇偶校验实现的方法：由若干位有效信息（如 1 B）再加上一个二进制位（校验位）组成校验码。校验位的取值（0 或 1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律。

奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
偶校验码：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

缺点：具有局限性，奇偶校验只能发现数据代码中奇数位的出错情况，但不能纠正错误，常用于对存储器数据的检查或传输数据的检查。

海明校验码

海明码是广泛采用的一种有效的校验码，它实际上是一种多重奇偶校验码。其实现原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，还能指出错位的位置，为自动纠错提供依据。根据纠错理论得：$$L- 1=D+C \ (D \ge C)$$即编码最小码距 $L$ 越大，其检测错误的位数 $D$ 越大，纠正错误的位数 $C$ 也越大，且纠错能力恒小于等于检错能力。海明码就是根据这一理论提出的具有纠错能力的一种编码。

下面用一个例子来介绍求海明码的步骤。在 $n=4$、$k=3$ 时，求 1010 的海明码。

（1）确定海明码的位数

设 $n$ 为有效信息的位数，$k$ 为校验位的位数，则信息位 $n$ 和校验位 $k$ 应满足 $$n+k \le 2^{k}-1$$ 若要检测两位错，则需再增加 1 位校验位，即 $k+1$ 位。海明码位数为 $n+k=7 \le 2^{3}-1$ 成立，则 $n$、$k$ 有效。

设信息位为 $D_{4} D_{3} D_{2} D_{1}$（1010），共 4 位，校验位为 $P_{3} P_{2} P_{1}$，共 3 位，对应的海明码为 $H_{7} H_{6} H_{5} H_{4} H_{3} H_{2} H_{1}$。

（2）确定校验位的分布

规定校验位 $P_i$ 在海明位号为 $2^{i-1}$ 的位置上，其余各位为信息位，因此有：

$P_1$ 的海明位号为 $2^{i-1} = 2^{0} = 1$，即 $H_1$ 为 $P_1$。
$P_2$ 的海明位号为 $2^{i-1} = 2^{1} = 2$，即 $H_2$ 为 $P_2$。
$P_3$ 的海明位号为 $2^{i-1} = 2^{2} = 4$，即 $H_4$ 为 $P_3$。

将信息位按原来的顺序插入，则海明码各位的分布如下:
$$
\begin{matrix}
H_{7} & H_{6} & H_{5} & H_{4} & H_{3} & H_{2} & H_{1} \\
D_{4} & D_{3} & D_{2} & P_{3} & D_{1} & P_{2} & P_{1}
\end{matrix}
$$

（3）分组以形成校验关系

每个数据位用多个校验位进行校验，但要满足条件：被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。另外，校验位不需要再被校验。分组形成的校验关系如下。

海明码校验位

（4）校验位取值

校验位 $P_i$ 的值为第 $i$ 组（由该校验位校验的数据位）所有位求异或（如果两个值不相同，则异或结果为 1。如果两个值相同，异或结果为 0。）。由上分组有：

$$
\begin{align*}
P_{1}=D_{1} \oplus D_{2} \oplus D_{4} = 0 \oplus 1 \oplus 1 = 0 \\
P_{2}=D_{1} \oplus D_{3} \oplus D_{4} = 0 \oplus 0 \oplus 1 = 1 \\
P_{3}=D_{2} \oplus D_{3} \oplus D_{4} = 1 \oplus 0 \oplus 1 = 0
\end{align*}
$$

所以，1010 对应的海明码为 1010010

（5）海明码的校验原理

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成 $k$ 个校验方程：

$$
\begin{align*}
S_{1}=P_{1} \oplus D_{1} \oplus D_{2} \oplus D_{4} \\
S_{2}=P_{2} \oplus D_{1} \oplus D_{3} \oplus D_{4} \\
S_{3}=P_{3} \oplus D_{2} \oplus D_{3} \oplus D_{4}
\end{align*}
$$

若 $S_{3}S_{2}S_{1} =000$，则说明无错；否则说明出错，且这个数就是错误的位号，如 $S_{3}S_{2}S_{1} = 001$，说明第 1 位出错，即 $H_{1}$ 出错，直接将该位取反就达到纠错的目的。

海明码校验元素关系

海明码的检错能力为 1 位，纠错能力为 2 位。通常使用时会在最头部加上“全校验位”，对整体进行偶校验：

$S_{3}S_{2}S_{1} =000$ 且全体偶校验成功，无错误
$S_{3}S_{2}S_{1} \ne 000$ 且全体偶校验失败，有 1 位错误，纠正即可
$S_{3}S_{2}S_{1} \ne 000$ 且全体偶校验成功，有 2 位称为，需重传

拓展：

【3Blue1Brown】汉明码Pa■t1，如何克服噪■

https://www.bilibili.com/video/BV1WK411N7kz

【3Blue1Brown】汉明码part2，优雅的全貌

https://www.bilibili.com/video/BV1pV411y7E8

循环冗余校验码

CRC 码的基本思想
如何构造
如何检错纠错

循环冗余校验（Cyclic Redundancy Check，CRC）码的基本思想是：在 $K$ 位信息码后再拼接 $R$ 位的校验码，整个编码的长度为 $N$ 位，因此，这种编码又称 $(N,K)$ 码。

数据发送、接收方约定一个“除数”
$K$ 个信息位 + $R$ 个校验位作为“被除数”，添加校验位后需保证除法的余数为 0
收到数据后，进行除法检查余数是否为 0，若余数非 0 说明出错，则进行重传或纠错

CRC 码基于线性编码理论，在发送端，将要传送的 $K$ 位二进制信息码左移 $R$ 位，将它与生成多项式 $G(x)$ 做模 2 除法，生成一个 $R$ 位校验码，并附在信息码后，构成一个新的二进制码（CRC 码），共 $K+R$ 位。在接收端，利用生成多项式对接收到的编码做模 2 除法，以检测和确定出错的位置，如无错则整除，其中生成多项式是接收端和发送端的一个约定。

任意一个二进制数码都可用一个系数仅为“ 0 ”或“ 1 ”的多项式与其对应。生成多项式 $G(x)$ 的最高幂次为 $R$，转换成对应的二进制数有 $R+1$ 位。例如，生成多项式 $x^{3} + x^{2} + 1$ 对应的二进制数为 1101，而二进制数 1011 对应的多项式为 $x^{3} + x^{2} + 1$ 。下面用一个例子来介绍 CRC 的编码和检测过程。

设生成多项式 $G(x) = x^{3} + x^{2} + 1$，信息码为 101001，求对应的 CRC 码

生成多项式 $G(x) = 1x^{3} + 1x^{2} + 0x^{1} + 1x^{0}$，故对应的二进制码为 1101。
$R$ 等于生成多项式最高次幂，即为 3
$K$ 等于信息码长度，即为 6
校验码位数 $N = K+R=9$

（1）位移

将原信息码左移 $R$ 位，低位补 0，得到 101001000

（2）相除

对位移后的信息码，用生成多项式进行模 2 除法，产生余数。

模 2 减法：和模 2 加法的结果相同，都是做异或运算
模 2 除法：模 2 除法和算术除法类似，但每位除（减）的结果不影响其他位，即不借位。

用除数对被除数最高几位做模 2 减（异或），不借位。
除数右移一位，若余数最高位为 1，商为 1，并对余数做模 2 减。若余数最高位为 0，商为 0，除数继续右移一位。
循环直到余数位数小于除数时，该余数为最终余数。

CRC码生成过程

模 2 除法过程如图上所示，得到余数为 001，则报文 101001 编码后的报文（即 CRC 码）为 101001001

（3）检错和纠错

接收端收到的 CRC 码，用生成多项式 $G(x)$ 做模 2 除法，若余数为 0，则码字无错。

若接收端收的 CRC 码为 $C_{9} C_{8} C_{7} C_{6} C_{5} C_{4} C_{3} C_{2} C_{1} = 101001011$，将这个数据与 1101 进行模 2 除法，得到的余数为 010，则说明 $C_{2}$ 出错（不一定正确），将 $C_{2}$ 取反即可。

注意：余数值与出错位置并不是二进制与十进制转换的关系。

CRC码余数与出错位关系

$K$ 个信息位，$R$ 个校验位，若生成多项式选择得当，且 $2^{R} \ge K + R + 1$ ，则 CRC 码可纠正 1 位错。实际应用中一般只用来“检错”。

理论上可以证明循环冗余校验码的检错能力有以下特点：

可检测出所有奇数个错误;
可检测出所有双比特的错误;
可检测出所有小于等于校验位长度的连续错误;

定点数的表示与运算

定点数的表示

无符号数和有符号数的表示

在计算机中参与运算的机器数有两大类：无符号（unsigned）数和有符号（signed）数。

无符号数。指整个机器字长的全部二进制位均为数值位，没有符号位，相当于数的绝对值。若机器字长为 8 位，则数的表示范围为 0 ~ 2⁸-1，即 0 ~ 255。
有符号数。在机器中，数的“正”“负”号是无法识别的，有符号数用“0”表示“正”号，用“1”表示“负”号，从而将符号也数值化，并通常约定二进制数的最高位为符号位，即将符号位放在有效数字的前面，组成有符号数。

有符号数的机器表示有原码、补码、反码和移码。为了能正确区别真值和各种机器数，约定用 X 表示真值，用 [X]_原表示原码，[X]_补表示补码， [X]_反表示反码，[X]_移表示移码。

机器数的的定点表示

定点表示即约定机器数中的小数点位置是固定不变的，小数点不再使用“.”表示，而是约定它的位置。理论上，小数点位置固定在哪一位都可以，但在计算机中通常采用两种简单的约定：将小数点的位置固定在数据的最高位之前，或固定在最低位之后。一般常称前者为定点小数，后者为定点整数。

（1）定点整数

定点整数是纯整数，约定小数点位置在有效数值部分最低位之后。若数据 $X$ 的形式为 $ X = x_{0}x_{1}x_{2} \cdots x_{n}$ （其中 $x_{0}$ 为符号位，$x_{1} \sim x_{n}$ 是数值的有效部分，也称尾数，$x_{n}$ 为最低有效位），则在计算机中的表示形式如图所示（设机器字长 $n+1$ 位)。

定点整数的格式

当 $x_{0}=0$，$x_{1} \sim x_{n}$，均为 1 时，$X$ 为其所能表示的最大正数，真值等于 $2^{n}-1$。
当 $x_{0}=1$，$x_{1} \sim x_{n}$，均为 1 时，$X$ 为其（原码）所能表示的最小负数，真值等于 $- ( 2^{-n}-1 )$。

（2）定点小数

定点小数是纯小数，约定小数点位置在符号位之后、有效数值部分最高位之前。若数据 $X$ 的形式为 $ X = x_{0}x_{1}x_{2} \cdots x_{n}$ （其中 $x_{0}$ 为符号位，$x_{1} \sim x_{n}$ 是尾数，$x_{1}$ 为最高有效位），则在计算机中的表示形式如图所示（设机器字长 $n+1$ 位)。

定点小数的格式

当 $x_{0}=0$，$x_{1} \sim x_{n}$，均为 1 时，$X$ 为其所能表示的最大正数，真值等于 $1-2^{-n}$。
当 $x_{0}=1$，$x_{1} \sim x_{n}$，均为 1 时，$X$ 为其（原码）所能表示的最小负数，真值等于 $- ( 1-2^{-n} )$。

原码、补码、反码、移码

原码表示法

原码是一种比较简单、直观的机器数表示法，用机器数的最高位表示该数的符号，其余的各位表示数的绝对值。原码的定义如下：

（1）纯整数的原码定义

$$[x]_\mathrm{原} = \begin{cases}
0, x & 2^{n} > x \ge 0 \\
2^{n}-x = 2^{n}+\left | x \right | & 0 \ge x > -2^{n}
\end{cases}$$

例如：

若 $x_{1}=+1110$，字长为 8 位，则其原码表示为 $[x_{1}]_\mathrm{原} = 00001110$，其中最高位是符号位。
若 $x_{2}=-1110$，字长为 8 位，则其原码表示为 $[x_{2}]_\mathrm{原} = 2^{7}+1110= 10001110$，其中最高位是符号位。

若字长为 $n+1$，则原码整数的表示范围为 $-(2^{n}-1) \le x \le 2^{n}-1$（关于原点对称）

注意：真值零的原码表示有正零和负零两种形式，即 $[+0]_\mathrm{原} = 00000$ 和 $[-0]_\mathrm{原} = 10000$。

（2）纯小数的原码定义

$$[x]_\mathrm{原} = \begin{cases}
x & 1 > x \ge 0 \\
1-x = 1+\left | x \right | & 0 \ge x > -1
\end{cases}$$

例如：

若 $x_{1}=+0.1101$，字长为 8 位，则其原码表示为：$[x_{1}]_\mathrm{原} = 01101000$，其中最高位是符号位。
若 $x_{2}=-0.1101$，字长为 8 位，则其原码表示为：$[x_{2}]_\mathrm{原} = 1-(-0.1101) = 11101000$，其中最高位是符号位。

更一般地：

对于正小数 $ x= +0.x_{1}x_{2} \cdots x_{n}$，有 $ [x]_\mathrm{原}= 0.x_{1}x_{2} \cdots x_{n}$
对于负小数 $ x= -0.x_{1}x_{2} \cdots x_{n}$，有 $ [x]_\mathrm{原}= 1.x_{1}x_{2} \cdots x_{n}$。

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

同样真值零的原码表示有正零和负零两种形式

反码表示法

反码通常用来作为由原码求补码或由补码求原码的中间过渡。

若符号位为 0，则反码与原码相同
若符号位为 1，则数值位全部取反

若字长为 $n+1$，反码的整数和小数表示范围与原码整数和小数表示范围对应相同。

注意：真值零的反码表示不唯一，$[+0]_\mathrm{反}=0.0000$，$[-0]_\mathrm{反}=1.1111$

补码

正数的补码 = 原码
负数的补码 = 反码末位 + 1（要考虑进位）

注意：补码的真值 0 只有一种表示形式 $[+0]_\mathrm{补}=[-0]_\mathrm{补}=00000000$，定点整数补码 $[x]_\mathrm{补}=10000000$ 表示 $x=-2^{7}$，定点小数补码 $[x]_\mathrm{补}=10000000$ 表示 $x=-1$

若机器字长为 $n+1$，补码整数的表示范围：$-2^{n} \le x \le 2^{n}-1$ （比原码多表示一个 $-2^{n}$）
若机器字长为 $n+1$，补码小数的表示范围：$-1 \le x \le 1-2^{-n}$ （比原码多表示一个 $-1$）

不同机器数之间的转换

移码

移码：补码的基础上将符号位取反。

注意：移码只能用于表示整数

移码的正值 0 和整数的表示范围与补码相同。

移码表示的整数很方便对比真值大小。

各种码的作用

（1）补码

用加法代替减法（时钟例子，模运算，将减法操作转换成与之等价的加法操作）

【前提知识】模运算的性质

带余数除法：设 $x,m \in Z,m >0$ 则存在唯一确定的整数 $q$ 和 $r$，使得：$x=qm+r , \ 0 \le r <m$

根据以上对余数的定义可得 $ -3 \bmod 12 = 9$，因为 $-3 = (-1) \times 12 + 9$ 。余数相同的数，可以认为是同一类数，是等价的。

互为补数：两个余数的绝对值之和对于模，这两个数互为补数，例如对于 12 取余可以得到 -3 和 9 ，这两个数绝对值之和对于 12，故称这两个数互为补数。a 的补数 = 模 - a 的绝对值

若能找到负数的补数，就可以用正数的加法来等价代替减法。

若一个 8 机器字节的计算机能够表示 $00000000 \sim 11111111$（ $0 \sim 2^{8}-1$ ），超出则直接舍弃，这就天然的实现了 $ \bmod 2^8$ 的运算，而补码就是补数。故补码实现了让减法操作转变为加法操作。

加减运算

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

溢出如何判断？

（二）移码

移码保持了数据原有的大小顺序，移码大真值就大，移码小真值就小。

定点数的运算

定点数的移位运算

移位运算根据操作对象的不同分为算术移位和逻辑移位。有符号数的移位称为算术移位，逻辑移位的操作对象是逻辑代码，可视为无符号数。

（1）算数移位

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

原码的算数移位：符号位保持不变，仅对数值位进行移位。

右移：在高位补 0，低位舍弃。若舍弃的位等于 0，则相当于除以 2；若舍弃的位不等于 0，则会丢失精度
左移：在低位补 0，高位舍弃。若舍弃的位等于 0，则相当于乘以 2 ；若舍弃的位不等于 0，则会出现严重误差

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

负数反码移位：

右移：高位补 1，低位舍弃。
左移：低位补 1，高位舍弃。

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

负数反码移位：

右移（同反码）：高位补 1，低位舍弃。
左移（同原码）：低位补 0，高位舍弃。

算数移位的应用举例

（2）逻辑移位

逻辑移位将操作数视为无符号数，移位规则：

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

应用举例：RGB 颜色 3 个 8 bit 数据，通过逻辑移位到对应的位置在进行相加，得到一个 24 bit 的数据。

（3）循环移位

循环移位分为带进位标志位 CF （进位位）的循环移位（大循环）和不带进位标志位的循环移位（小循环）

循环移位的主要特点是，移出的数位又被移入数据中，而是否带进位则要看是否将进位标志位加入循环位移。例如，带进位位的循环左移就是数据位连同进位标志位一起左移，数据的最高位移入进位标志位 CF，而进位位则依次移入数据的最低位。

循环移位

循环移位操作特别适合将数据的低字节数据和高字节数据互换。

原码定点数的加减运算

加法规则：

先判符号位，若相同，则绝对值相加，结果符号位不变；（可能会出现溢出的情况）
若不同，则做减法，绝对值大的数减去绝对值小的数，结果符号位与绝对值大的数相同。

减法规则：两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。

补码定点数加减运算

补码加减运算规则简单，易于实现，因此计算机系统中普遍采用补码加减运算。补码运算的特点如下（设机器字长为 n+1）。

参与运算的两个操作数均用补码表示。
按二进制运算规则运算，逢二进一。
符号位与数值位按同样规则一起参与运算，符号位运算产生的进位要丢掉，结果的符号位由运算得出。
补码加减运算依据下面的公式进行。当参加运算的数是定点小数时，模 $M=2$；当参加运算的数是定点整数时，模 $M= 2^{n+1}$。$$[A+B]_\mathrm{补} = [A]_\mathrm{补} +[B]_\mathrm{补} (\bmod M)$$$$[A-B]_\mathrm{补} = [A]_\mathrm{补} +[-B]_\mathrm{补} (\bmod M) $$

注意：$\bmod M$ 运算是为了将溢出位丢掉。

也就是说，若做加法，则两数的补码直接相加；若做减法，则将被减数与减数的机器负数相加。
补码运算的结果亦为补码。

溢出概念和判别方法

溢出是指运算结果超过了数的表示范围。

称大于机器所能表示的最大正数为上溢。正数 + 正数 = 负数
称小于机器所能表示的最小负数为下溢。负数 + 负数 = 正数

仅当两个符号相同的数相加或两个符号相异的数相减才可能产生溢出，如两个正数相加，而结果的符号位却为 1 （结果为负）；一个负数减去一个正数，结果的符号位却为 0 （结果为正）。定点数加减运算出现溢出时，运算结果是错误的。

补码定点数加减运算溢出判断的方法有3种。

（1）采用一位符号位

由于减法运算在机器中是用加法器实现的，因此无论是加法还是减法，只要参加操作的两个数符号相同，结果又与原操作数符号不同，则表示结果溢出。设 $A$ 的符号为 $A_s$，$B$ 的符号为 $B_s$，运算结果的符号为 $S_s$ 则溢出逻辑表达式为 $$V = A_{s} B_{s} \overline{S_{s}} + \overline{A_{s}} \overline{B_{s}} S_{s}$$ 若 $V = 0$ ，表示无溢出；若 $V = 1$ ，表示有溢出。

（2）采用一位符号位根据数据位的进位情况判断溢出

若符号位的进位 $C_s$ 与最高数位的进位 $C_1$ 相同，则说明没有溢出，否则表示发生溢出。溢出逻辑判断表达式为 $$V = C_{s} \oplus C_{1}$$ 若$V=0$ ，表示无溢出；$V=1$，表示有溢出。

（2）采用双符号位

双符号位法也称模 4 补码。运算结果的两个符号位 $S_{s1} S_{s2}$ 相同，表示未溢出；运算结果的两个符号位 $S_{s1} S_{s2}$ 不同，表示溢出，此时最高位符号位代表真正的符号。

符号位 $S_{s1} S_{s2}$ 的各种情况如下:

$S_{s1} S_{s2} = 00$：表示结果为正数，无溢出。
$S_{s1} S_{s2} = 01$：表示结果正溢出。
$S_{s1} S_{s2} = 10$：表示结果负溢出。
$S_{s1} S_{s2} = 11$：表示结果为负数，无溢出。

溢出逻辑判断表达式为 $$V = S_{s1} \oplus S_{s2}$$ 若 $V=0$，表示无溢出；若 $V=1$，表示有溢出。

符号扩展

在计算机算术运算中，有时必须把采用给定位数表示的数转换成具有不同位数的某种表示形式。例如，某个程序需要将一个 8 位数与另外一个 32 位数相加，要想得到正确的结果，在将 8 位数与 32 位数相加之前，必须将 8 位数转换成 32 位数形式，这称为“符号扩展”。

正数的符号扩展非常简单，即原有形式的符号位移动到新形式的符号位上，新表示形式的所有附加位都用 0 进行填充。

负数的符号扩展方法则根据机器数的不同而不同。

原码表示负数的符号扩展方法与正数相同，只不过此时符号位为 1。
补码表示负数的符号扩展方法：原有形式的符号位移动到新形式的符号位上，新表示形式的所有附加位都用 1（对于整数）或 0（对于小数）进行填充。
反码表示负数的符号扩展方法：原有形式的符号位移动到新形式的符号位上，新表示形式的所有附加位都用 1 进行填充。

定点数的乘法运算

在计算机中，乘法运算由累加和右移操作实现。根据机器数的不同，可分为原码一位乘法和补码一位乘法。原码一位乘法的规则比补码一位乘法简单。

（1）原码一位乘法

原码一位乘法的特点是符号位与数值位是分开求的，乘积符号由两个数的符号位“异或”形成，而乘积的数值部分则是两个数的绝对值相乘之积。设 $[X]_\mathrm{原} = x_{s} x_{1} x_{2} x_{3} \cdots x_{n}$ ， $[Y]_\mathrm{原} = y_{s} y_{1} y_{2} y_{3} \cdots y_{n}$ ，则运算规则如下：

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

由于乘积的数值部分是两数绝对值相乘的结果，因此原码一位乘法运算过程中的右移操作均为逻辑右移。

注意：考虑到运算时可能出现绝对值大于 1 的情况（但此刻并非溢出），所以部分积和被乘数取双符号位。

（2）补码的一位乘法（Booth 算法）

这是一种有符号数的乘法，采用相加和相减操作计算补码数据的乘积。设 $[X]_\mathrm{补} = x_{s} x_{1} x_{2} x_{3} \cdots x_{n}$ ， $[Y]_\mathrm{补} = y_{s} y_{1} y_{2} y_{3} \cdots y_{n}$ ，则运算规则如下：

符号位参与运算，运算的数均以补码表示。
被乘数一般取双符号位参与运算，部分积取双符号位，初值为0，乘数可取单符号位。
乘数末位增设附加位 $y_{n+1}$ ，且初始值为 0。
根据 $(y_{n},y_{n+1})$ 的取值来确定操作。
移位按补码右移规则进行。
按照上述算法进行 $n+1$ 步操作，但第 $n+1$ 步不再移位（共进行 $n+1$ 次累加和 $n$ 次右移），仅根据 $y_n$ 与 $y_{n+1}$ 的比较结果做相应的运算。

定点数的除法运算

在计算机中，除法运算可转换成“累加-左移”（逻辑左移），根据机器数的不同，可分为原码除法和补码除法。

（1）原码除法运算（恢复余数法）

商符和商值是分开进行的，商符由两个操作数的符号位“异或”形成。

视频链接

左移 $n$ 次，上商 $n+1$ 次，最后一次上商余数不左移

（2）原码除法运算（不恢复余数法）

原码除法主要采用原码不恢复余数法，也称原码加减交替除法。特点是商符和商值是分开进行的，商符由两个操作数的符号位“异或”形成。求商值的规则如下：

若最后一步余数为负数，需要“恢复余数”

加/减 $n+1$ 次，每次加减确定一位商；左移 $n$ 次（最后一次加减完不移位）最终可能还要再多一次加。

该方法只适用于商小于 1 的除法

（3）补码除法运算（加减交替法）

补码一位除法的特点是，符号位与数值位一起参加运算，商符自然形成。除法第一步根据被除数和除数的符号决定是做加法还是减法；上商的原则根据余数和除数的符号位共同决定，同号上商“1”，异号上商“0”；最后一步商恒置“1”。

加减交替法的规则如下：

符号位参加运算，除数与被除数均用补码表示，商和余数也用补码表示。
若被除数与除数同号，则被除数减去除数；若被除数与除数异号，则被除数加上除数。
若余数与除数同号，则商上 1，余数左移一位减去除数；若余数与除数异号，则商上 0，余数左移一位加上除数。
重复执行第 3 步操作 n 次。
若对商的精度没有特殊要求，则一般采用“末位恒置 1”法。

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

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

#include "stdio.h"

int main() {
    // 无符号数与有符号数：不改变数据内容，改变解释方式。
    short x = -4321;  // short 型占用 2 个字节
    // x : 1110 1111 0001 1111
    // y : 1110 1111 0001 1111 真值为 61215
    unsigned short y = (unsigned short)x;

    // 长整数变短整数：高位截断，保留低位
    int a = 165537, b = -34991;  // int 型占用 4 个字节
    // a: 0x000286a1 -> c: 0x86a1 真值为 -31071
    // b: 0xffff7751 -> d: 0x7751 真值为 30545
    short c = (short)a, d = (short)b;  // short 型占用 2 个字节

    // 短整数变长整数：符号扩展
    short e = -4321;
    // e: 1110 1111 0001 1111                     0xef1f
    // m: 1111 1111 1111 1111 1110 1111 0001 1111 0xffffef1f 真值为 -4321
    int m = e;
    // n: 1110 1111 0001 1111                     0xef1f     真值为 61215
    unsigned short n = (unsigned short)e;
    // p: 0000 0000 0000 0000 1110 1111 0001 1111 0x0000ef1f 真值为 61215
    unsigned int p = n;

    printf("x = %d \t 0x%x \n", x, x);
    printf("y = %d \t 0x%x \n", y, y);
    printf("\n");
    printf("a = %d \t 0x%x \n", a, a);
    printf("c = %d \t 0x%x \n", c, c);
    printf("b = %d \t 0x%x \n", b, b);
    printf("d = %d \t 0x%x \n", d, d);
    printf("\n");
    printf("e = %d \t 0x%x \n", e, e);
    printf("m = %d \t 0x%x \n", m, m);
    printf("n = %d \t 0x%x \n", n, n);
    printf("p = %d \t 0x%x \n", p, p);

    return 0;
}

有符号数和无符号数的转换

int main(){
    short x = -4321;
    unsigned short y = (unsigned short)x;
    printf("x = %d, y = %u \n", x ,y);
    // x = -4321, y = 61215
}

强制类型转换的结果保持位值不变，仅改变了解释这些位的方式。

不同字长整数之间的转换

当大字长变量向小字长变量强制类型转换时，系统把多余的高位字长部分直接截断，低位直接赋值，因此也是一种保持位值的处理方法。

而短字长到长字长的转换，在位值相等的条件下还要补充高位的符号位，可以理解为数值的相等。注意，char 类型为 8 位 ASCII 码整数，其转换为 int 时，在高位部分补 0 即可。

数据的存储和排列

数据的“大端方式”和“小端方式”存储

在存储数据时，数据从低位到高位可以按从左到右排列，也可以按从右到左排列。因此，无法用最左或最右来表征数据的最高位或最低位，通常用最低有效字节（LSB）和最高有效字节（MSB）来分别表示数的低位和高位。例如，在 32 位计算机中，一个 int 型变量 i 的机器数为 01 2345 67H，其最高有效字节 MSB = 01H，最低有效字节 LSB = 67H。

现代计算机基本上都采用字节编址，即每个地址编号中存放 1 字节。不同类型的数据占用的字节数不同，int 和 float 型数据占 4 字节，double 型数据占 8 字节等，而程序中对每个数据只给定一个地址。假设变量 i 的地址为 80 00H，字节 01H、23H、45H、67H 应该各有一个内存地址，那么地址 08 00H 对应 4 字节中哪字节的地址呢？这就是字节排列顺序问题。多字节数据都存放在连续的字节序列中，根据数据中各字节在连续字节序列中的排列顺序不同，可以采用两种排列方式:大端方式（big endian）和小端方式（little endian）。

大端方式按从最高有效字节到最低有效字节的顺序存储数据，即最高有效字节存放在前面；（符合人类阅读习惯）
小端方式按从最低有效字节到最高有效字节的顺序存储数据，即最低有效字节存放在前面。（便于机器处理）

数据按“边界对齐”方式存储

假设存储字长为 32 位，可按字节、半字和字寻址。对于机器字长为 32 位的计算机，数据以边界对齐方式存放，半字地址一定是 2 的整数倍，字地址一定是 4 的整数倍，这样无论所取的数据是字节、半字还是字，均可一次访存取出（每次访存只能读/写 1 个字）。所存储的数据不满足上述要求时，通过填充空白字节使其符合要求。这样虽然浪费了一些存储空间，但可提高取指令和取数的速度。（空间换时间）

数据不按边界对齐方式存储时，可以充分利用存储空间，但半字长或字长的指令可能会存储在两个存储字中，此时需要两次访存，并且对高低字节的位置进行调整、连接之后才能得到所要的指令或数据，从而影响了指令的执行效率。

边界对齐方式相对边界不对齐方式是一种空间换时间的思想。RISC 如 ARM 采用边界对齐方式，而 CISC 如 x86 对齐和不对齐都支持。因为对齐方式取指令时间相同，因此能适应指令流水。

浮点数的表示与运算

浮点数的表示

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

浮点数的表示格式

通常，浮点数表示为：$$N=r^{E} \times M$$ 式中，$r$ 是浮点数阶码的底（隐含），与尾数的基数相同，通常 $r = 2$。$E$ 和 $M$ 都是有符号的定点数，$E$ 称为阶码，$M$ 称为尾数。可见浮点数由阶码和尾数两部分组成。

阶码是整数，阶符 $J_{f}$ 和阶码的位数 $m$ 共同反映浮点数的表示范围及小数点的实际位置；阶码常用补码或移码表示的定点整数。
数符 $S_{f}$ 代表浮点数的符号，尾数的位数 $n$ 反映浮点数的精度。尾数常用原码或补码表示的定点小数

规格化浮点数

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

左规：当浮点数运算的结果为非规格化时要进行规格化处理，将尾数算术左移一位、阶码减 1 （基数为 2 时）的方法称为左规，左归可能要进行多次。
右规：当浮点数运算的结果尾数出现溢出（双符号位为 01 或 10 ）时，将尾数算术右移一位、阶码加 1（基数为 2 时）的方法称为右规。需要右归时，只需进行一次。

注：采用“双符号位”，当溢出发生时，可以挽救。更高的符号位是正确的符号位

规格化浮点数的尾数 $M$ 的绝对值应满足条件 $\frac{1}{r} \le |M| \le 1$。若 $r=2$，则有 $\frac{1}{2} \le |M| \le 1$。规格化表示的尾数形式如下：

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

正数为 $0.1 \cdots$ 的形式，其最大值表示为 $0.11 \cdots 1$，最小值表示为 $0.100 \cdots 0$ 。尾数的表示范围为 $\frac{1}{2} \le M \le (1-2^{-n})$
负数为 $1.1 \cdots$ 的形式，其最大值表示为 $1.10 \cdots 0$ ，最小值表示为 $1.11 \cdots 1$。尾数的表示范围为 $-(1-2^{-n}) \le M \le - \frac{1}{2}$

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

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

浮点数的表示范围

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

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

IEEE 754 标准

按照 IEEE 754 标准，常用的浮点数的格式如下所示：

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

IEEE 754 偏置值为 $2^{n-1}-1$

以短浮点数为例，最高位为数符位；其后是 8 位阶码，以 2 为底，用移码表示，阶码的偏置值为 $2^{8-1}-1= 127$；其后 23 位是原码表示的尾数数值位。对于规格化的二进制浮点数，数值的最高位总是“1”，为了能使尾数多表示一位有效位，将这个“1”隐含，因此尾数数值实际上是 24 位。隐含的“1”是一位整数。

IEEE 754 标准中，规格化的短浮点数的真值为 $(-1)^{s} \times 1.M \times 2^{E-127}$ 。规格化长浮点数的真值为 $(-1)^{s} \times 1.M \times 2^{E-1023}$ 式中：

$s=0$ 表示正数，$s= 1$ 表示负数；
短浮点数 $E$ 的取值为1 ～ 254（ 8 位表示），$M$ 为 23 位，共 32 位；
长浮点数 $E$ 的取值为 1～2046 ( 11 位表示)，$M$ 为 52 位，共 64 位。

单精度浮点型，当阶码 $E$ 全为 0，尾数 $M$ 不全为 0 时，表示非规格化小数。（隐含最高位变为 0，阶码真值固定视为 -126）
当阶码 $E$ 全为 0，尾数 $M$ 全为 0 时，表示真值 $\pm 0$ ，数符位判断正负
当阶码 $E$ 全为 1，尾数 $M$ 全为 0 时，表示无穷大 $\pm \infty $，数符位判断正负
当阶码 $E$ 全为 1，尾数 $M$ 不全为 0 时，表示非数值 NaN（Not a Number），如进行 0/0 等非法运算的结果

定点、浮点表示的区别

数值的表示范围：若定点数和浮点数的字长相同，则浮点表示法所能表示的数值范围将远远大于定点表示法。

精度：所谓精度，是指一个数所含有效数值位的位数。对于字长相同的定点数和浮点数来说，浮点数虽然扩大了数的表示范围，但精度降低了。

数的运算：浮点数包括阶码和尾数两部分，运算时不仅要做尾数的运算，还要做阶码的运算，而且运算结果要求规格化，所以浮点运算比定点运算复杂。

溢出问题：在定点运算中，当运算结果超出数的表示范围时，发生溢出；浮点运算中，运算结果超出尾数表示范围却不一定溢出，只有规格化后阶码超出所能表示的范围时，才发生溢出。

浮点数的加减运算

浮点数运算的特点是阶码运算和尾数运算分开进行。浮点数的加减运算一律采用补码。浮点数加减运算分为以下几步。

对阶

对阶的目的是使两个操作数的小数点位置对齐，即使得两个数的阶码相等。为此，先求阶差，然后以小阶向大阶看齐的原则，将阶码小的尾数右移一位（基数为 2），阶加 1，直到两个数的阶码相等为止。尾数右移时，舍弃掉有效位会产生误差，影响精度。