408计组-数据表示和运算

0. 数据存储

位（bit，符号为 b）是计算机中最小的信息单位。

字节（byte，符号为 B）是基本的存储和寻址单位。8 位一个字节。

参考计网

字是一个架构层面的约定，一个字可能表示 2、4 或 8 字节。

字长（也成为机器字长）指 CPU 内部整数运算的数据通路的宽度，通常也等于通用寄存器的宽度，也即指针占用的内存空间大小。反应计算机一次能处理的整数数据的位数。常见的是 32 位和 64 位。

小/大端法：

• 小端法：最低有效字节（LSB）放在内存的前面（与阅读顺序相反）。
• 大端法：最高有效字节（MSB）放在内存的前面（与阅读顺序相同）。
• 大多数机器使用小端法。
• 大端还是小端是针对字节的，而不是针对位的。
• 字符串类型在内存中的储存顺序与大端法还是小端法无关。

对齐

为了提高内存读写效率，数据之间需要进行对齐。对齐原则是任何 $K$ 字节的基本对象的地址必须是 $K$ 的倍数。

C 语言中的结构体内有多种数据类型。结构体的内存布局需要遵循下述对齐规则：

• 每个成员的起始地址必须是其对齐值的整数倍。

• 整个结构体的大小必须是其最大成员对齐值的整数倍（不足则在尾部填充）。

  这么做的原因是，1 2 4 8 这四个数，后面的数字都是前面的数字的倍数，比如按 8 对齐之后自然满足按 2 对齐，但是按 2 对齐后未必能是按 8 对齐的，所以我们要取对齐的最大值

比如：

• struct P1 {int i;char c;int j;char d;};

偏移	0	4	8	12	16	对齐
内容	int i;	char c; + 填充	int j;	char d; + 填充		4

注意最后大小不是 9，d 后面还有 3 字节的填充。这么做是因为我们希望做到 P1 类型后面再跟一个 P1 类型的话，后面 P1 类型的第一个成员也满足对齐

• struct P2 {int i;char c;char d;long j;};

偏移	0	4	5	8	16	对齐
内容	int i;	char c;	char d; + 填充	long j;		8

• struct P3 {short w[3];char c[3];};

偏移	0	6	10	对齐
内容	short w[3];	char c[3]; + 填充		2

这个例子最后的填充说明，数组需要对齐的倍数为数组元素的大小而并非整个数组的大小

• struct P4 {short w[5];char *c[3];};

偏移	0	16	40	对齐
内容	short w[5]; + 填充	char c[3];		8

• struct P5 {struct P3 a[2];struct P2 t;};

偏移	0	24	40	对齐
内容	struct P3 a[2]; + 填充	struct P2 t;		8

1. 数制

数字后添加后缀字母来标识进制：B 表示二进制、O 表示八进制、D 表示十进制（通常省略）、H 表示十六进制。

不同进制转换

• 二进制与八进制/十六进制互换

  整数部分，从小数点向左，每 $3$ 位（八进制）或每 $4$ 位（十六进制）分为一组（如果向左不足 $3$ 位或者 $4$ 位则在高位补 $0$）。小数部分，从小数点向右每 $3$ 位或 $4$ 位分成一组，不足则在低位补 $0$。分组完成后，将每组直接替换为对应的八进制或十六进制数即可。

​ 八进制与十六进制转为二进制时，即把对应的数码变为 $3$ 位或是 $4$ 位的二进制数。

​ 八进制和十六进制相互转换时，最好是先转成二进制，然后再进行转换。

• 十进制转任意进制数

  对于整数部分使用除基取余法，不断除以目标进制的基数，记录余数，直至商为 $0$。最先得到的余数为最低位，最后得到的为最高位。

  对于小数部分使用乘基取整法，不断乘以基数，记录整数部分，直至小数部分为 $0$。最先得到的整数为最高位，最后得到的为最低位。

  qq_pic_merged_1773665456865

  并非所有的十进制小数都可以被有限位二进制精确表示，只有可以被表示成形如 $\frac{k}{2^n}$ 的分数的十进制小数才可以。像是 $0.3$ 就不行。对应地，任何有限位二进制小数都对应一个分母为 $2$ 的幂的分数，因此总能精确地转换为十进制小数。

2. 编码

机器数：数字在计算机中的表示。

真值：机器数所代表的实际数值。

2.1 定点数

二进制表示中，最左边的位为符号位，剩余的位为数值部分。数值部分的最左边的位为最高有效位，最右边的位为最低有效位。

最高有效位和最高位有没有区别感觉不太好把握。比如这里的符号位是最高位，但不是最高有效位。

机器的内部表示中并没有小数点，小数点是人为的（相当于数据类型）。

2.1.1 原码

最高位表示数的符号，其余各位表示数的绝对值。

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

其中 $x$ 为真值。字长为 $n+1$。

表示范围为 $-(2^n-1)\le x \le 2^n-1$，关于原点对称。

零的原码表示有正零和负零两种。

原码实现乘法和除法比较简单，实现加法和减法比较困难。

加法规则：如果是同号的，结果的符号位就取这个相同的符号，然后再把数值位相加，如果相加完了之后向符号位进位了，就说明发生了溢出。如果是异号的，比较两者的绝对值，结果的符号位取绝对值最大的数的符号，然后再把绝对值较大的数值位减去绝对值较小的数值位。

减法规则：把被减数取相反数，再去应用加法规则。

由于原码的加法操作存在比较绝对值大小这一步，逻辑比较复杂，所以现代计算机普遍使用补码。

2.1.2 补码

又称为 2 的补码，或是模 2 补码。

$$\left [ x \right ]_{\text{补}} = \begin{cases} 0, x & 0 \le x < 2^n \\ 2^{n+1} + x = 2^{n+1} - \left | x \right | & -2^n \le x < 0 \end{cases}$$

其中 $x$ 为真值。字长为 $n+1$。

等价地，无论是正数还是负数，均有 $\left [ x \right ]_{\text{补}} = 2^{n+1} + x$。将正数和负数均视为一个无符号整数进行运算，自然溢出，就相当于是在模 $2^{n+1}$ 意义下进行运算，所以补码表示可以直接运算。

从位的角度上，最高位的贡献为 $-2^{n}$。

表示范围为 $-2^n\le x \le 2^n - 1$，比原码多表示一个负数 $-2^n$。

正数的补码表示和原码相同。负数的补码表示为其对应的正数的补码表示按位取反，再加 $1$。

变形补码

也被称为补码的双符号位表示，或者是模 4 补码。

变形补码在高位有两个符号位，两个符号位相同。相加时可以直接根据这两个符号位来判读溢出情况，也就是后面的双符号位检测溢出。

模 4 补码有模 2 补码的全部有点且更容易检查加减，包括乘除运算中的溢出问题。

由于正常的模 4 补码的两个符号位总是相同的，所以存储时也是只需要存储 1 个符号位，只有在 ALU 中运算时才需要两个符号位。

2.1.3 反码

又称为 1 的补码。

反码可视为真值转成对应补码的中间表示。

正数的反码与其原码相同。负数的反码由其原码的数值部分按位取反（如果再加 $1$ 就变成了补码）。

反码的 $0$ 也是有两种表示方式。

2.1.4 移码

移码是将真值 $x$ 加上一个偏置值。如果字长为 $n+1$ 位，偏置值通常取 $2^n$：

$$\left [ x \right ]_{\text{移}} = 2^n + x$$

表示范围为 $-2^n\le x < 2^n$。

在 IEEE 754 标准中，阶码也用移码表示，但是 $n+1$ 位的阶码的偏置值为 $2^n-1$

移码的符号位取反即可得到补码。

表示范围为 $-2^n\le x \le 2^n - 1$。移码全 $0$ 时，对应的真值的最小值 $-2^n$。移码全 $1$ 时，对应真值的最大值 $2^n-1$。

---

正数的原码、反码、补码相同，移码不同。

移码能直接在位表示上反应出大小关系，其他的编码方式则不能。原码能够直观的比较大小，数值部分即为绝对值。补码和反码，在符号位相同的前提下，数值部分越大，其对应真值也越大。

2.1.5 类型转换

long （long int），在 32 位系统中为 32 位，在 64 位系统中通常为 64 位。

相同字长的转换，不改变位表示，仅改变解释方式。

• 有符号数转无符号数

  $$T2U_w(x)=\begin{cases} x+2^w, & x<0 \\ x, & x \ge 0 \end{cases}$$

• 无符号数转有符号数

  $$U2T_w(x)=\begin{cases}x, & x\le T_{max} \\x-2^w, & x > T_{max}\end{cases}$$

​ 符号位为 $0$，两者转换前后相同。反之，转化前后相差 $2^w$。

• 有符号和无符号同时出现时

  在C语言中，有符号和无符号同时出现时，会隐式地将有符号转为无符号。

短类型转换为长类型：位扩展。

• 零扩展：无符号整数扩展时，高位补0。

• 符号扩展：有符号整数扩展时，补原最高位，类似逻辑右移。

• 扩展前后对应的真值是不变的。

长类型转换为短类型，直接把高位截断。

当既有有符号和无符号的转换，又有扩展或者截断时，要先改变大小，再进行有符号和无符号之间的转换。这是C语言标准规定的。

2.2 浮点数

现代系统普遍采用 IEEE754 浮点数标准。

2.2.1 规格化数

对于一个小数 $b$，我们可以将其表示为一个二进制的小数：

$$b_mb_{m-1}...b_1b_0.b_{-1}b_{-2}...b_{-n+1}b_{-n}$$

然后，类似于科学计数法，我们把小数点挪到前面去，仅保留最左边的有效位：

$$b_m.b_{m-1}...b_1b_0b_{-1}b_{-2}...b_{-n+1}b_{-n}$$

$b_m$ 必然是 $1$，因此我们不存储 $b_m$，只存储后面的 $n+m$ 个位。这些位我们称之为尾数，记为 $M$，使用原码编码。

我们把小数点向左移动了 $m$ 位。使用移码来编码这个 $m$。我们将移码编码后的机器数称之为阶码，记为 $E$。

阶码不用补码的原因：IEEE754 的设计者在最开始希望浮点数的大小能直接通过位的角度来比较，而补码显然不满足这一点。

IEEE 754 中 $n$ 位的阶码的偏置值为 $2^{n-1}-1$。

再使用单独的符号位来表示正负。

浮点数的表示为：

其中单精度格式对应的补码偏置值为 $127$，双精度格式对应的补码偏置值为 $1023$。

对于单精度浮点数，其对应的真值为：

$$(-1)^s\times 1.M \times 2^{E-127}$$

对于双精度浮点数，其对应的真值为：

$$(-1)^s\times 1.M \times 2^{E-1023}$$

上面两个式子中的 $2$ 表示基数。浮点数中的基数固定为 $2$。

阶码部分如果全为 $1$ 或者是全为 $0$ 就不表示规格化数了。

2.2.2 非规格化数

非规格化数用于表示非常接近于 $0$ 的小数。

规格化数中，尾数实际上是有一个隐藏位 $1$，而非规格化数没有隐藏位。同时，非规格化数的表示中，阶码看起来 $0$，但这里 $E$ 取 $1$

于是单精度非规格化数的真值为：

$$(-1)^s\times 0.M \times 2^{1-127}$$

双精度非规格化数的真值为：

$$(-1)^s\times 0.M \times 2^{1-1023}$$

2.2.3 其他格式

阶码	尾数	说明
全 $0$	全 $0$	表示真值 $0$。IEEE 754 中的 $0$ 有 $+0$ 和 $-0$ 两种。
全 $0$	不全 $0$	表示非规格化数
既不全 $0$ 也不全 $1$	——	表示规格化数
全 $1$	全 $0$	表示 $\infty$。根据符号位，分成 $+\infty$ 和 $-\infty$ 两种
全 $1$	不全 $0$	表示 NaN，一般是计算发生了错误，比如对负数开根。

一些架构可能会在 NaN 的尾数部分编码更多的信息来描述 NaN 是如何产生的。但这属于标准之外的东西，不同的架构有不同的实现。

位数相同的定点数和浮点数，定点数能表示的数值更多。因为 $n$ 位编码最多表示 $2^n$ 个不同的比特模式。定点数通常能表示 $2^n$ 个互异的有效数值，而浮点数中部分编码用于表示 $\pm0$、$\pm\infty$，NaN 等特殊数值，实际可以表示的有效实数个数小于 $2^n$。

2.2.4 加减运算

对阶

首先要对阶，让两个操作数的小数点位置是对齐的，便于后面直接对尾数相加减。

对阶的原则是小阶向大阶看齐。阶码较小的操作数可以右移尾数部分（即左移小数点）来使得阶码增加。

如果阶码较小的操作数是规格化数的话，尾数在右移的时候，隐藏位也会被移进来。

尾数中由于右移被移出去的部分不会被直接丢掉，而是会放到辅助位上，用于后面的舍入。

不能是大阶向小阶看齐，这样的话相当于小数点右移，小数点左边的数没地方放。

尾数加减

对于规格化数，运算的时候要把隐藏位还原到尾数部分，也就是要带着隐藏位来进行计算。

用于舍入的辅助位也要参与运算。

本质上就是定点原码小数的加减运算。不过实际上计算机的硬件上没有原码运算的硬件实现。硬件会直接把尾数视为无符号数，送入通用 ALU 进行加减运算。

尾数规格化

先对尾数的运算结果进行规格化：

• 右规

  尾数相加之后可能得到这种结果：1x.xx...x，小数点左边有两个数，此时需要进行右规。

  尾数右移一位，阶码加 $1$。然后最高位 $1$ 去掉，作为隐藏位。

  最后一位被移出时，需要考虑舍入。

  尾数相加之后，小数点左边最多只有两个数，所以必然只需要右移一次。

• 左规

  尾数相减之后可能得到这种结果：0.00...01x...x，此时需要进行左规。

  尾数每左移一次，阶码减 $1$，可能需要左移多次，直到第一位 $1$ 移到小数点左边。

  左移的时候要把辅助位的也给移进来。

规格化之后，进行舍入（不是规格化之前进行舍入）。

舍入之后，有可能因为给尾数最低位上面加 $1$ 了，导致尾数再次不是规格化的了，于是还需要再右规一次。

2.2.5 舍入

在对阶和右规的过程中，尾数右移可能导致低位丢失。为了保证精度，低位丢失时需要对浮点数进行舍入。

IEEE754 引入如下三个辅助位来指导舍入：

• 保护位（G）：紧邻尾数最低位有效位之后的第一位。当尾数最低位被右移出去之后，会先放到保护位上面。
• 舍入位（R）：位于保护位之后。保护位被右移出去之后，会先放到舍入位上面。
• 粘滞位（S）：舍入位之后被移除的位的或，即舍入位之后被移出的位中存在至少一个 $1$，粘滞位就为 $1$，反之则为 $0$。

IEEE754 定义了如下四种可选择的舍入模式：

• 就近舍入（默认方式）：选择最接近真实值的可表示数（即四舍六入）。如果正好位于两个可表示的数中间，则选择尾数最低有效位为 $0$ 的那个（偶数）。
  • 如果保护位为 $0$，说明更靠近小的数，直接把辅助位舍去
  • 如果保护位为 $1$
    • 如果舍入位为 $1$ 或者粘滞位为 $1$，说明更靠近大的数，尾数加 $1$
    • 如果保护位和粘滞位均为 $0$，说明位于两个数中间了，向偶舍入。即如果尾数末尾为 $1$ 则给尾数加 $1$。
• 正向舍入：朝数轴 $+\infty$ 方向舍入。
• 负向舍入：朝数轴 $-\infty$ 方向舍入。
• 朝原点舍入：即直接把辅助位舍去。

值得注意的是，这里的 $R$ 是必要的，可以使得左规之后再舍入是对的。需要左规时，一定是两个浮点数相减。设大的浮点数为 $A$，小的浮点数为 $B$，那么会有如下两种情况：

• 当两个数的阶码相差很大（$\ge 2$ 时）

  $B$ 的尾数必须右移至少 $2$ 位，此时 $B$ 的低位会掉进 G、R、S 中。但是，比如 $A$ 尾数形如 1.000...，$B$ 右移两位后最大也只是 0.011...，相减，得到 0.1xxx... 或者是 1.0xxx 这个样子。总之，后面再左规的时最多只需要左移 $1$ 位。

  左移的时候，G 被移进来了。原来的 R 到了现在的 G 的位置，由于原来的 R 就是精准的，所以现在的 G 还是精准的。

  原来的 S 到了现在的 R 的位置，原来的 S 不精准，所以现在的 R 也不精准。但是，上面的舍入规则看的是“舍入位为 $1$ 或者粘滞位为 $1$”或者是“如果保护位和粘滞位均为 $0$”，而如今的 R 即使不精准，但是仅凭 R 本身（也就是原来的 S）也能精准地判断出这两个规则谁是符合的，所以不影响舍入。

  而假如说我们没有 R，那么会导致左移之后 G 就是不准的了，G 到底是 0 还是 1 无法判断，也就无法判断怎么舍入。

• 如果两个数的阶码相差为 $0$ 或是 $1$ 时，此时两个数非常接近，相减之后出现了大量的 $0$，比如 0.0000001。此时需要左移很多位来左规。

  但是：

  • 如果阶码相差 $0$，根本不需要对阶，也就是没有位掉进 GRS 里，左规时直接低位补 $0$，是没有引入任何误差的。
  • 如果阶码相差 $1$，对阶时只有只有一位小数掉进了 G 中，后面再左规，$G$ 移入进来之后后面再直接补 $0$，也是没有引入任何误差的。

对于两个单精度浮点数相加，如果两个操作数阶码之差的绝对值 $\ge 25$，则结果直接取阶码较大的操作数。

证明：阶码相差大于等于 $25$ 的话，即使较小操作数是规格化数，其最高位的 $1$ （也就是隐藏位）也被右移到了较大操作数 R 位置及其之后。此时相加，无论较小操作数是什么，都改变不了结果的 G 位，结果的 G 位永远为 $0$，永远都是直接向下舍入的。

而如果是两个单精度浮点数相减，那么阶码之差绝对值要 $\ge 26$ 才能使得结果直接取阶码较大的操作数。

证明：

首先，如果阶码之差为 $25$，那么被减数的 GSR 部分为 000，减数对阶之后 GSR 部分为 0xx。可能出现这种情况：被减数的最低有效位为 $1$，减数的 GSR 部分为 010。那么相减之后，结果的最低有效位变为了 $0$ （被 GSR 部分借位了），然后结果的 GSR 部分为 100。此时向偶舍入，结果的最低有效位还是为 $0$ 。结果和被减数不一致。

如果阶码之差为 $26$，那么有两种情况：

• 减数的 GSR 部分为 000，这个是显然的。
• 减数的 GSR 部分为 001，相减之后，会从 GSR 前面的位借 $1$，结果的 GSR 变为 110，于是又向上舍入，导致 GSR 前面的位又进了 $1$，于是结果和被减数保持一致。

这个题说的是加减，但是答案给的 $25$，我认为不太对。

2.2.6 溢出

浮点数溢出本质上是阶码超出可表示范围而导致的（尾数超过可表示范围属于舍入的问题）

• 上溢（也直接称为溢出）

  当浮点运算结果的绝对值超过最大规格化数的时候发生。比如浮点数相加后结果 $\ge 2$，或者是舍入后结果又 $\ge 2$，这两种情况下都会导致左规，从而使得阶码 $+1$。如果原阶码已为最大正规格化值，那么溢出就发生了。

  如果结果为正且大于最大规格化正数，则称为正溢出。如果结果为负且小于最小规格化负数，则称为负溢出。

  IEEE754 对溢出的处理规则：

  • 将结果设置为 $+\infty$ 或者是 $-\infty$。
  • 设置浮点溢出异常标志。
  • IEEE754 规定，默认情况下不触发异常中断，程序继续执行，除非显式开启此类异常响应。

• 下溢

  当浮点运算结果的绝对值小于最小规格化正数但不为 $0$ 时发生。一般是发生在尾数相减，然后左规时，尾数不断左移，然后阶码一直减 $1$。当减到 $-126$（对于单精度）或是 $-1022$ （对于双精度）时，再减下去，就变成了非规格化数，此时我们称之为发生了渐进下溢。

  非规格化数的设计可以使得规格化数平滑地进入非规格化数。同时非规格化数的分布是均匀的，

  如果运算结果小到连非规格化数都表示不下，此时就说明发生了指数下溢，IEEE754 对其进行如下处理：

  • 将结果设置为 $+0$ 或是 $-0$。
  • 设置浮点下溢异常标志。
  • 同样地默认不触发异常中断，除非显式开启。

2.2.7 类型转换

浮点数和整数混合运算时，会先把整数隐式转换为浮点数。

当 int 转 float 时，虽然不会发生溢出，但是由于 float 尾数（含隐藏位）仅 24 位有效，而 int 为 32 位，因此当整数的二进制有效位超过 24 位时，需要进行舍入处理，导致精度损失。

int 和 float 转 double，由于后者有效位更多，所以通常能精确地表示。

double 转 float 时，一方面 float 的表示范围较小，大数值转换可能会发生溢出（涉及到阶码）。另一方面，float 的尾数有效位变少，还会发生舍入误差（涉及到尾数）。

float 或 double 转 int 时，小数部分会直接丢弃。同时，如果浮点数值超出 int 表示范围，还会发生整数溢出（未定义行为）。

3. 运算与电路

3.1 加法

3.1.1 溢出判断

无符号整数

位数为 $w$ 时，$x$ 和 $y$ 相加，得到 $(x+y)\space mod \space 2^w$。即如果要溢出了就减去 $2^w$。

设得到的结果为 $s$，如果 $s<x$ 或者 $s<y$，则说明发生了溢出。

有符号整数

位数为 $w$ 时，$x$ 和 $y$ 相加，如果发生了正溢出就减去 $2^w$，如果发生了负溢出就加上 $2^w$。

设得到的结果为 $s$

• 当 $x>0$，$y>0$，但 $s\le 0$ 时，说明发生了正溢出。
• 当 $x<0$，$y<0$，但 $s\ge 0$ 时，说明发生了负溢出。

3.1.2 一位全加器

输入：当前位的两个加数 $A_i$ 和 $B_i$，来自低位的进位 $C_{i-1}$。

输出：本位的加和结果 $S_i$，向高位的进位 $C_i$。

$$\begin{align} S_i &= A_i\oplus B_i\oplus C_{i-1} \\ C_i &= A_iB_i+(A_i\oplus B_i)C_{i-1} \end{align}$$

3.1.3 串行进位加法器

又称行波进位加法器。

最后一位溢出，直接舍掉，相当于进行模 $2^n$（$n$ 为加法器位数）的加法。

3.1.4 并行进位加法器

又称为先行进位加法器/超前进位加法器。

考虑到每一位的进位值：

$$\begin{align} C_1 &= A_1B_1+(A_1\oplus B_1)C_{0} \\ C_2 &= A_2B_2+(A_2\oplus B_2)C_{1} \\ C_3 &= A_3B_3+(A_3\oplus B_3)C_{2} \\ \dots \\ C_i &= A_iB_i+(A_i\oplus B_i)C_{i-1} \end{align}$$

我们把不依赖前面的进位值的部分提出来：

$$\begin{align} P_i &= A_iB_i \\ Q_i &= A_i\oplus B_i \\ \end{align}$$

然后每一位的进位值展开：

$$\begin{align} C_1 &= P_1+Q_1C_{0} \\ C_2 &= P_2+Q_2(P_1+Q_1C_{0}) \\ C_3 &= P_3+Q_3(P_2+Q_2(P_1+Q_1C_{0})) \\ \dots \\ C_i &= P_i+Q_i(P_{i-1}+Q_{i-1}(P_{i-2}+Q_{i-2}(\dots))) \end{align}$$

这样每一个进位值就都是独立的了，可以在电路上并行计算。

这样展开之后的算式看起来很复杂，实际上电路也确实复杂（），但是电路是分级的，同一级上可以并行计算，所以速度上并不会太慢：

电路大概会分成 $O(\log n)$ 级，于是进行一个加法操作只需要 $O(\log n)$ 的时间，优于串行进位加法器的 $O(n)$ 的时间。

3.1.5 标志

在完成加法操作的情况下还生成如下的标志：

• 溢出标志：OF

  $OF=C_n\oplus C_{n-1}$，其中 $C_{n-1}$ 为向符号位的进位输入，$C_n$ 为符号位的进位输出。

  用于判断有符号数（将输入的二进制位视为补码时）的加法运算是否溢出，OF 为 1 表示溢出，为 0 表示没溢出。对于无符号数的运算来说没有意义。

  只有两个同号的数相加才会发生溢出（相减视为对相反数相加）。如果是两个正数相加发生溢出，那么 $A_{n-1}=B_{n-1}=0$，$C_{n-1}=1$，得到 $C_n=0$。如果是两个负数相加发生溢出，在 $n-2$ 这一位上不进位$C_{n-1}=0$，$A_{n-1}=B_{n-1}=1$，$C_{n}=1$。

  溢出标志还有别的计算方法：

  • 当两个操作数的符号位相同，但是结果的符号位不同时，说明发生溢出（正数相加溢出必然得到负数，负数相加溢出必然得到正数）

    $OF=A_SB_S\overline{S_S}+\overline{A_SB_S}S_S$

  • 搞两个符号位，$A_{S1}A_{S2}$，$A_{S1}$ 是高位，$A_{S2}$ 是低位。$A_{S2}$ 即为原来的符号位，$A_{S1}$ 和 $A_{S2}$ 相同，相当于是一个备份。对于 $B$ 也同理。运算后，观察运算结果的符号位 $S_{S1}S_{S2}$。

    $OF=S_{S1}\oplus S_{S2}$

    道理类似 $OF=C_n\oplus C_{n-1}$。$S_{S1}S_{S2}=00$ 表示正数相加没溢出，$S_{S1}S_{S2}=11$ 表示负数相加没溢出，$S_{S1}S_{S2}=01$ 表示正数相加溢出，$S_{S1}S_{S2}=10$ 表示负数相加溢出。

• 符号标志：SF

  $SF=F_{n-1}$，即结果的符号位。

  用于判断运算结果的正负性，SF 为 1 表示负数，为 0 表示正数。

• 零标志：ZF

  用于判断结果是否为 0。

• 进位/借位标志：CF

  $CF=C_{in}\oplus C_{n}$，其中 $C_{in}$ 为初始的进位输入，$C_n$ 为符号位的进位输出。

  用于判断无符号数（将输入的二进制位单纯地视为无符号数时）的加法运算是否溢出，CF 为 1 表示溢出，为 0 表示没溢出。对于有符号数的运算来说没有意义。

  在做加法时，有 $C_{in}=0$，如果溢出了，那么必然有 $C_n=1$。在做减法时，有 $C_{in}=1$，减法在没溢出时，反而是 $C_n=1$，$C_n=0$ 则反而是说明减法溢出了。

这些标志可以用来判断两个数字的大小。比如现在对于两个数字 $A$ 和 $B$ 进行 $A-B$ 的运算，得到了标识位：

• 如果 $ZF=1$，说明 $A=B$

• 如果 $ZF=0$

  • 如果 $A$ 和 $B$ 是无符号的，继续看 $CF$
    • 如果 $CF=0$，说明 $A>B$
    • 如果 $CF=1$，说明 $A<B$
  • 如果 $A$ 和 $B$ 是有符号的，继续看 $OF$ 和 $SF$
    • 如果 $OF=0$
      • 如果 $SF=0$，说明结果是非负的，说明 $A>B$
      • 如果 $SF=1$，说明结果是负的，说明 $A<B$
    • 如果 $OF=1$
      • 如果 $SF=0$，说明必然是负数减去正数发生溢出，导致结果变正了，说明 $A<B$
      • 如果 $SF=1$，说明必然是正数减去负数发生溢出，导致结果变负了，说明 $A>B$
    • 总结起来就是，如果 $OF\oplus SF=0$，说明 $A>B$。如果 $OF\oplus SF=1$，说明 $A<B$

3.2 减法

硬件中的加法是在模 $2^n$ 意义下进行的。对于一个二进制的 $n$ 位数 $x$，对其按位取反，再加 $1$，即可得到 $x$ 在模 $2^n$ 意义下的减法逆元。

在做减法的时候，只需要将减数按位取反，同时将 $C_0$ 设为 $1$，即可用加法器做减法。

上面这些，无论数字是有符号还是无符号都适用。

数字的有无符号性取决于上层对二进制编码的解释。由于补码有 $\left [ x \right ]_{\text{补}} = 2^{n+1} + x$，所以其天然地适配于硬件上自然的加法。

3.3 逻辑

ALU

提供按位或和按位与操作，然后和加法操作合在一块，根据多路复用器来选择输出哪个操作的结果。

实际上的 ALU 还会包含 xor 和 not 操作。不过只有 and 和 or 也能完成 xor 和 not（对 -1 取 xor 即可）。

ALU 中的核心组件是加法器。

3.4 移位

3.4.1 移位运算

对于无符号数使用逻辑移位：

• 左移：高位移出，低位补 $0$。如果高位的 $1$ 移出，则发生溢出。
• 右移：低位移出，高位补 $0$。

对于有符号数使用算数移位：

• 左移：高位移出，低位补 $0$。如果左移后的符号位发生了改变，则发生溢出。
• 右移：低位移出，高位补符号位。

3.4.2 移位寄存器

移位运算就不在 ALU 里面做了，而是有专门的硬件。

朴素的做法是使用移位寄存器，可以在每个周期移位一次。下图是一个四位的移位寄存器，每个时钟周期右移（向 $Q_4$ 方向）一次。

3.4.3 桶形移位器

当然这样的效率非常低。更好的选择是桶形移位器。下图是一个八位的桶形移位器：

din 为数据输入。shamt 表示要移位的次数。L/R 表示左移还是右移，为 $1$ 为左移，为 $0$ 为右移。A/L 表示逻辑移位还是算数移位，为 $1$ 为算数移位，为 $0$ 为逻辑移位。

对应电路：

和超前进位加法器类似，也是通过电路的分级来减少时间开销。第 $i$ 层来把输入进行 $2^{i-1}$ 的移位，相当于对 shamt 进行二进制拆分来做。同时，桶形移位器是纯组合电路实现的，一个周期内就能完成。

3.5 乘法

3.5.1 无符号乘法电路

如果手算一个二进制数（不考虑符号），可以直接沿用十进制乘法的方法列竖式计算。

根据这个方法可以得到无符号数乘法的运算电路：

图中的 $C$、$P$ 和 $Y$ 实际上是同一个寄存器的最高位、高位部分和低位部分。

对于 $A\times B$ 这个运算，初始时：

• $A$ 存到 $X$ 这个寄存器中。
• $B$ 存到 $Y$ 这个寄存器中。$Y$ 寄存器随着运算的进行，会存放最后乘积的结果。
• $C_n = 32$
• $P$ 寄存器清零

接下来会不断循环如下的过程：

• 首先将 $Y$ 的最低位送入控制逻辑，控制逻辑对最低位进行判断。如果最低位为 $1$，则将 $Y$ 加到 $P$ 上，如果产生了进位，那么这个进位就放到 $C$ 中。如果最低位为 $0$，则不进行任何操作。
• 将 $C$、$P$、$Y$ 作为一个整体进行逻辑右移。
• 将 $C_n$ 减一。如果 $C_n$ 被减到 $0$ 则结束这个循环，否则就继续下一轮循环。

这个过程相当于是最后的结果右移，由于被乘数不动，所以被乘数相对于结果是左移的，于是就和上面竖式的过程对上了。

如果最后 $P$ 中不全为 $0$ 的话，则说明最后的运算结果用 $32$ 位存不下，发生溢出。

3.5.2 有符号乘法电路

这个电路基于 Booth 算法。Booth 算法其实是一个优化算法，用来减少乘法过程中相加的次数，只不过可以恰好用于处理补码中的符号位。

比如说我们有二进制 $00111100$，这个可以表示为 $01000000 - 00000100$，在对第 $3$ 位（右边第一个是第 $1$ 位）相减时，会一直向前借位，然后就导致了中间这一连续的一段变为了全 $1$。

考虑一组从位位置 $l$ 到位位置 $r$ 的连续的 $1$（$l\le r$），这一部分对乘积的影响有如下两种形式：

• $(x<<l)+(x<<(l+1))+...+(x<<r)$
• $(x<<(r+1))-(x<<l)$

Booth 算法就是通过把第一种形式转为第二种形式，减少了乘数中的 $1$ 的个数，从而使得加法次数变少，不过又同时引入了减法操作。

和上面的电路差不多，区别在于，这里在 $Y$ 的最低位的右边又引入了一个辅助位 $y_{-1}$。$y_{-1}$ 初始值为 $0$。$P$、$Y$ 和 $y_{-1}$ 还是应该在右移的时候视为一个整体。

在循环时，$Y$ 的最低位 $y_0$ 和辅助位 $y_{-1}$ 组成一个两位的二进制码，送入控制逻辑：

• 如果 $y_0y_{-1}=00$ 或是 $y_0y_{-1}=11$，则进行空操作。$y_0y_{-1}=00$ 可以视为和之前一样的行为。$y_0y_{-1}=11$ 可以视为，现在要跳过连续的 $1$ 的段。
• 如果 $y_0y_{-1}=10$，说明我们后面会遇到一个连续的 $1$ 段，所以根据我们上面所说，这里要先减一下。于是就有了 $P=P-X$。
• 如果 $y_0y_{-1}=01$，说明我们已经扫完了前面的一个连续的 $1$ 段，所以根据我们上面所说，这里要加一下。于是就有了 $P=P+X$。

同时，这个电路的右移是算数右移。

Booth 算法能够处理掉补码中符号位的原因是，对于负数，其补码表示会有一段前缀 $1$ 段。而上述的运算过程中，遇到这个前缀 $1$ 段时会先减去当前位的贡献。正常来说，后面我们扫过去连续 $1$ 段，再加上更高位的贡献后，总贡献就相当于是原来连续 $1$ 段内所有 $1$ 应该有的贡献。但是由于我们这个是前缀 $1$ 段，后续是碰不到 $y_0y_{-1}=01$ 的情况了，所以只有减的贡献，没有加的贡献，而这个减的贡献又恰好对应于补码。

如果最后，$P$ 中所有的位和 $Y$ 中的最高位符号不同，则判定为溢出。

3.5.3 溢出

发生溢出后，CPU 会将 $OF$ 和 $CF$ 同时置 $1$。

此外 CPU 不进行任何处理。乘法的溢出处理属于软件层面的操作，如果需要对溢出进行特殊处理的话，可以在乘法指令后面加入判断逻辑。

在编程语言上，对于 $x$ 和 $y$ 相乘，令其结果为 $p$。如果 $x$ 为 $0$，显然不会发生溢出。反之，如果 p / x != y 则说明发生溢出。

3.5.4 乘法运算实现

• 迭代式乘法器：就是上面提到的。
• 阵列乘法器：大概意思应该是类似于桶形移位器和超前进位加法器一样，并行地算出需要计算的所有部分。整个电路只有组合逻辑，可以在单时钟周期内完成。
• 移位-加减法：乘法运算可以通过移位和加减法的方式（模拟上面电路的方法）在软件层面实现。

3.6 除法

3.6.1 除以2的幂

无符号

对于除以 $2^k$ 且下取整，直接逻辑右移 $k$ 位即可。

有符号

对于除以 $2^k$ ，如果直接算数右移 $k$ 位，那么得到的结果是向下取整的。

但C语言中的负数做除法时，并不是向下取整，是向零取整的。

当被除数为正时，没什么问题。

当被除数为负时，我们需要先加上一个偏置值 $2^k-1$，再算数右移 $k$ 位。

3.6.2 运算电路

二进制除法手算也是和十进制是一样的，不断地试商：

对应的电路：

对于 $A/B$ 这个操作，初始时需要先进行一系列特判：

• $B$ 不能为 $0$，否则会发生异常。
• $|A|<|B|$ 时，商为 $1$，余数为 $B$。
• 对于有符号数，还需要特判商溢出的情况。在两个 $n$ 位补码除法中，商溢出有且仅有一种情况：$A$ 为最大负数 $-2^{n-1}$ 且 $B$ 为 $-1$，此时得到的结果 $2^{n-1}$ 无法用 $n$ 位补码表示。

如果是无符号数，我们有如下的过程：

首先对寄存器进行初始化：

• 寄存器 $Y$ 中存放 $B$。
• 寄存器 $Q$ 中的低 $32$ 位存放 $A$，高 $32$ 位为 $0$。寄存器 $Q$ 在运算过程中会逐步形成最后的商。
• 寄存器 $R$ 置为 $0$，用于存放余数。
• 计数器 $C_n$ 置为 $32$。

然后不断进行下面的循环：

• 先将 $Q$ 和 $R$ 视为一个整体，做逻辑左移，然后 $Q$ 的最低位用来接收新的商位。
• 然后将 $R$ 减去 $Y$，如果结果大于等于 $0$，那么将 $Q$ 的最低位置为 $1$。反之，置为 $0$，同时再把 $R$ 加上 $Y$。（相当于试商，没试好就再回复）。
• 将 $C_n$ 减一，如果 $C_n$ 减到 $0$ 就结束循环。

如果是有符号数，运算过程会存在如下差异：

• $A$ 需要先做符号扩展，扩展到 $64$ 位，然后放入到 $Q$ 中。
• $R$ 初始时所有的位初始化为 $A$ 的符号位。
• 循环时执行的是算数左移（虽说和逻辑左移没区别）。
• 有符号数的试商过程会比较麻烦，408 不考，所以就不学了（）

3.6.3 异常处理

当发生除 $0$ 或者是商溢出的异常时，CPU 会设置异常标识，然后由硬件自动地通过中断向量表跳转至预设的异常处理程序。

4. 错题

0 也行，所以选择 D。

A 选项是商溢出的情况，B 是被除数绝对值小于除数绝对值的情况，这两种情况都是会被开始时特判调的，所以理论上执行时间都挺短的。不过商溢出的情况应该更容易特判，所以 A 应该更对，但是答案给的 B ，似乎有点问题。

采用规格化的浮点是最主要是为了增加数据的表示精度。

对于 Ⅰ，x + y 是可能发生整数溢出的，而 dx + dy 是不会发生溢出的。

对于 Ⅳ，可以直接用舍入那里的结论，f 和 d 的阶码之差显然大于了 $25$，因此 d+f==d。

注意 employee[1].id 位于 C4，同时意味着 78H 位于 C4

（感觉答案有点问题，在第二步那里没有带上隐藏位进行运算）

对于 （2），考虑到 x 和 y 都是可以用机器数表示出来的，所以可以先计算 x+y 和 x-y 然后再转成浮点数机器码。