# 计算机组成原理实战：用Python模拟乘法运算的底层实现（附完整代码） 很多学习计算机组成原理的朋友，可能都曾在“乘法运算”这一章感到困惑。课本上那些关于原码、补码、Booth算法的流程图和规则描述，虽然逻辑严谨，但总感觉隔着一层纱，难以想象这些抽象的规则是如何在真实的CPU电路里“跑”起来的。我自己当年学这部分时，也有同样的感觉，直到后来尝试用代码去模拟这些过程，才真正有种“哦，原来是这样”的通透感。 这篇文章，就是为你准备的这样一次“通透之旅”。我们不满足于仅仅理解理论规则，而是要亲手用Python代码，把CPU执行乘法运算的几种核心算法——原码一位乘、补码一位乘（校正法）和Booth算法——从零搭建出来。你会发现，那些看似复杂的“部分积”、“右移”、“末位判断”，本质上就是一系列巧妙的位运算和移位操作的组合。通过代码的逐行执行和中间状态的打印，你能像调试程序一样，清晰地看到每一次加法、每一次移位是如何改变寄存器中的数据的，从而直观地理解硬件底层的运作逻辑。无论你是计算机专业的学生，还是对底层技术有浓厚兴趣的爱好者，这次动手实践都将让你对“计算机如何计算”有更深刻的认识。 ## 1. 从笔算到机器运算：理解乘法的核心挑战 在深入代码之前，我们有必要先厘清一个根本问题：为什么CPU不能像我们人类笔算乘法那样直接进行运算？想象一下我们计算 `13 * 9 = 117` 的过程。我们会将 `13` 乘以 `9` 的每一位，得到若干个“部分积”，然后将这些部分积错位相加。对于二进制乘法，比如 `1101 (13) * 1001 (9)`，过程也是类似的。 ```python # 一个简化的笔算乘法思维过程 (13 * 9) 被乘数 = 0b1101 # 13 乘数 = 0b1001 # 9 # 笔算步骤（心理过程）： # 1. 乘数最低位是1，所以记下被乘数 1101 # 2. 乘数次低位是0，记下 0000 # 3. 乘数第三位是0，记下 0000 # 4. 乘数最高位是1，记下被乘数 1101 # 5. 将所有记下的数按位左移后相加： # 1101 (对应乘数位0，左移0位) # 0000 (对应乘数位0，左移1位) # 0000 (对应乘数位0，左移2位) # 1101 (对应乘数位1，左移3位) # --------- # 1110101 (117的二进制) ``` > 注意：上面的代码只是一个思维演示，并非可执行的算法。它揭示了笔算乘法的两个关键特征：**需要存储多个中间结果（部分积）** 和 **需要进行多次错位加法**。 对于人类来说，在纸上保留多个中间结果并逐步相加是容易的。但对于早期的计算机硬件来说，这却是个大问题。设计能够同时处理多个操作数并进行复杂错位加法的电路，成本高昂且效率低下。因此，计算机工程师们设计出了一系列**迭代算法**，其核心思想是：**将乘法分解为一系列“加法-移位”的重复步骤，每一步只处理一位乘数，并且只保留一个累积的“部分积”**。 这个转变是理解所有硬件乘法算法的钥匙。它意味着： * **空间效率**：无需为所有中间部分积准备存储空间，只需少数几个寄存器。 * **时间效率**：通过简单的、重复的电路操作（加法器、移位器）完成复杂计算。 * **控制简单**：可以用一个统一的控制逻辑（循环）来驱动整个计算过程。 下面的表格对比了笔算思维与机器算法思维的核心差异： | 特性 | 人类笔算乘法 | 机器迭代算法（如原码一位乘） | | :--- | :--- | :--- | | **中间结果** | 多个部分积同时存在 | 只有一个累积的部分积 | | **加法次数** | 一次复杂的多操作数求和 | 多次简单的两操作数求和 | | **硬件需求** | 需要多操作数加法器，电路复杂 | 只需一个标准的双操作数加法器，电路简单 | | **过程控制** | 无固定流程，依赖人的判断 | 固定的“判断-加-移位”循环 | 理解了这一设计哲学，我们再去看原码一位乘、补码乘法等具体算法，就不会觉得它们是一堆生硬的规则，而是一个为了解决特定硬件约束而诞生的、非常巧妙的工程方案。 ## 2. 基石算法：原码一位乘法的Python实现 原码一位乘法是最直观、最易于理解的硬件乘法算法。它直接操作数字的**绝对值**（即原码的数值部分），符号位单独处理（同号为正，异号为负）。其算法流程可以精炼为以下几步，我们将围绕这个流程构建代码： 1. **初始化**：设置部分积寄存器 `P` 为0，乘数寄存器 `MQ` 存放乘数的绝对值，被乘数寄存器 `X` 存放被乘数的绝对值。计数器 `count` 等于数值位的位数 `n`。 2. **循环判断与累加**：检查乘数 `MQ` 的当前最低位（`MQ[0]`）。 * 如果为1，则将部分积 `P` 加上被乘数 `X`。 * 如果为0，则 `P` 不变。 3. **联合右移**：将 `P` 和 `MQ` 视为一个整体进行算术右移一位。`P` 的最低位移入 `MQ` 的最高位，`MQ` 的最低位移出丢弃。 4. **更新与循环**：计数器 `count` 减1。如果 `count > 0`，则跳回第2步继续循环。 5. **组合结果**：循环结束后，`P` 中的内容是乘积的高位部分，`MQ` 中的内容是乘积的低位部分。将它们组合起来，再根据原始两数的符号位确定最终乘积的符号。 让我们用Python来实现它。为了清晰展示每一步的状态变化，我们会让函数打印出详细的中间过程。 ```python def unsigned_one_bit_multiply(multiplicand, multiplier, n_bits=4): """ 模拟无符号数原码一位乘法（数值部分运算）。 Args: multiplicand: 被乘数（正整数）。 multiplier: 乘数（正整数）。 n_bits: 操作数的二进制位数（默认4位）。 Returns: 乘积的数值部分。 """ # 初始化：使用固定位宽，确保移位操作正确 P = 0 # 部分积寄存器 X = multiplicand # 被乘数寄存器 MQ = multiplier # 乘数寄存器 count = n_bits # 计数器 print(f"开始无符号原码一位乘法: {X} * {MQ} (位宽={n_bits})") print(f"初始化: P={P:0{n_bits}b}, X={X:0{n_bits}b}, MQ={MQ:0{n_bits}b}, count={count}") for i in range(n_bits): # 1. 判断乘数最低位 lsb = MQ & 1 print(f"\n--- 第 {i+1} 轮循环 ---") print(f" 检查MQ最低位: {lsb}") old_P = P # 2. 根据最低位决定是否加被乘数 if lsb == 1: P = P + X print(f" MQ最低位为1，执行 P = P + X: {old_P} + {X} = {P}") else: print(f" MQ最低位为0，P保持不变: {P}") # 3. 联合右移: (P, MQ) 整体右移1位 # 先将P和MQ组合成一个临时变量 combined = (P << n_bits) | MQ combined = combined >> 1 # 分离出新的P和MQ P = combined >> (n_bits - 1) # 右移后，高n_bits位是新的P MQ = combined & ((1 << n_bits) - 1) # 低n_bits位是新的MQ print(f" 联合右移后: P={P:0{n_bits}b}, MQ={MQ:0{n_bits}b}") # 组合最终结果：乘积 = (P << n_bits) | MQ product = (P << n_bits) | MQ print(f"\n运算结束。") print(f"乘积数值部分: {product} (二进制: {product:0{2*n_bits}b})") return product # 测试：计算 13 * 9 (使用4位表示，实际会溢出，但算法过程正确) # 注意：4位无符号数最大为15，13*9=117远超范围，这里主要演示过程。 print("="*50) result = unsigned_one_bit_multiply(0b1101, 0b1001, n_bits=4) ``` 运行这段代码，你会看到每一步`P`和`MQ`的变化。然而，上面的实现有一个问题：它没有处理加法可能导致的**中间溢出**。在实际硬件中，部分积寄存器 `P` 的位宽会比被乘数多一位，以容纳加法过程中的进位。让我们改进一下，实现一个更贴近硬件、能处理符号位的完整原码一位乘法。 ```python def signed_magnitude_one_bit_multiply(x_int, y_int, n=4): """ 完整的带符号原码一位乘法实现。 Args: x_int, y_int: 十进制整数输入，可正可负。 n: 数值部分的位宽（不包括符号位）。 Returns: 乘积的十进制结果。 """ # 1. 分离符号和数值 sign_x = 0 if x_int >= 0 else 1 sign_y = 0 if y_int >= 0 else 1 x_mag = abs(x_int) y_mag = abs(y_int) # 乘积符号：同号为0，异号为1 (异或运算) sign_product = sign_x ^ sign_y # 2. 初始化寄存器 (部分积P需要n+1位，以存放加法进位) P = 0 # n+1 位宽的部分积，初始为0 X = x_mag # n 位宽的绝对值 MQ = y_mag # n 位宽的绝对值，同时作为乘数寄存器 count = n print(f"\n开始带符号原码一位乘法: {x_int} * {y_int}") print(f"绝对值: |X|={X}({X:0{n}b}), |Y|={MQ}({MQ:0{n}b})") print(f"符号位: sign_x={sign_x}, sign_y={sign_y}, 乘积符号={sign_product}") print(f"初始化: P={P:0{n+1}b}, MQ={MQ:0{n}b}, count={count}") # 3. 主循环 for i in range(count): lsb = MQ & 1 print(f"\n[步骤 {i+1}] MQ最低位 = {lsb}") if lsb == 1: # 执行加法，P是n+1位，X是n位，需要对齐 P = P + X print(f" 执行 P + X: {P-X:0{n+1}b} + {X:0{n}b} = {P:0{n+1}b}") else: print(f" MQ最低位为0，P保持不变: {P:0{n+1}b}") # 联合右移 (P和MQ) # 首先，将P的最低位移入MQ的最高位 # 将P和MQ组合： (P有n+1位，MQ有n位) -> 总共2n+1位 # 简单做法：将P看作高n+1位，MQ看作低n位，右移后，P的高n位成为新的P，低1位和MQ组成新的MQ combined = (P << n) | MQ combined = combined >> 1 # 新的P是combined的高n位（实际上，因为右移了，原P的n+1位变成了n位高+1位低） # 更准确：新的P是原P右移1位（算术右移，高位补0） P = P >> 1 # 这是算术右移，对于正数（P始终非负），高位补0 # MQ的新高位是原P的最低位，MQ自身右移 bit_from_P = (combined >> (n-1)) & 1 # 从组合中提取移入MQ最高位的那个位 MQ = ((combined & ((1 << n) - 1)) >> 1) | (bit_from_P << (n-1)) print(f" 右移后: P={P:0{n+1}b}, MQ={MQ:0{n}b}") # 4. 组合结果 # 最终乘积的数值部分：P是高位，MQ是低位 magnitude_product = (P << n) | MQ # 加上符号位 final_product = magnitude_product if sign_product == 0 else -magnitude_product print(f"\n计算完成。") print(f"乘积数值部分: {magnitude_product} (二进制: {magnitude_product:0{2*n}b})") print(f"最终乘积（含符号）: {final_product}") return final_product # 测试用例 print("="*50) signed_magnitude_one_bit_multiply(7, 3, n=4) # 7 * 3 = 21 print("="*50) signed_magnitude_one_bit_multiply(-7, 3, n=4) # -7 * 3 = -21 ``` 这个改进版本更真实地模拟了硬件行为，包括符号位的独立处理和对部分积寄存器位宽的考虑。通过运行这些代码，你可以清晰地看到，原码一位乘如何通过简单的循环，将复杂的乘法化为加法与移位的舞蹈。 ## 3. 处理正负数的通用方案：补码一位乘法（校正法） 原码乘法虽然直观，但有一个明显的缺点：符号需要单独处理，这对于设计统一的算术逻辑单元（ALU）来说不够优雅。现代计算机普遍使用补码表示有符号整数，因为它允许加法和减法使用同一套电路。那么，乘法呢？补码乘法是否也能做到统一？ 补码一位乘法（校正法）就是为此而生的。它的核心思想是：**直接对补码进行操作，最终得到的就是乘积的补码**。算法在原码一位乘的基础上，根据乘数的符号进行“校正”。其规则可以概括为： * 如果乘数 `Y` 的补码为正（符号位为0），则算法流程与原码一位乘完全相同，只是操作数都是补码形式。 * 如果乘数 `Y` 的补码为负（符号位为1），则先将其**符号位忽略**，按原码规则与 `|X|` 的补码（即 `X` 本身，如果X为正）进行运算，得到中间结果。最后，**加上 `[-X]补` 进行校正**，才能得到正确的 `[X*Y]补`。 > 提示：校正法的“校正”步骤，本质上是因为当乘数为负时，我们实际上是在计算 `X * ( -|Y| )`。按原码算的是 `X * |Y|`，所以需要最后减去 `X * |Y|` 的补码，即加上 `[- (X * |Y|)]补`，而 `[- (X * |Y|)]补` 在特定条件下可以转化为最后一步加 `[-X]补` 来实现。 让我们用Python来实现这个算法。为了简化，我们假设操作数都在一定范围内，并使用固定位宽。 ```python def twos_complement_corrective_multiply(x_int, y_int, n=4): """ 补码一位乘法（校正法）实现。 注意：此实现假设输入整数在n位补码可表示范围内。 """ # 转换为n位补码表示（使用位运算模拟） def to_twos_complement(val, bits): if val >= 0: return val & ((1 << bits) - 1) else: return ((1 << bits) + val) & ((1 << bits) - 1) # 2^bits + val X = to_twos_complement(x_int, n) Y = to_twos_complement(y_int, n) print(f"\n开始补码一位乘法（校正法）: {x_int} * {y_int}") print(f"补码表示: [X]补 = {X:0{n}b}, [Y]补 = {Y:0{n}b}") # 判断乘数Y的符号 sign_y = (Y >> (n-1)) & 1 # 取最高位为符号位 # 初始化 P = 0 # 部分积，初始为0 # 被乘数：如果使用校正法，当Y为负时，运算过程中实际使用的是 |X| 的补码。 # 对于正数X，[|X|]补 = [X]补。 # 对于负数X，[|X|]补 = [-X]补，我们需要计算这个值。 if x_int >= 0: X_mag_tc = X # [|X|]补 neg_X_tc = to_twos_complement(-x_int, n) # [-X]补，用于校正 else: # X为负， |X| = -x_int X_mag_tc = to_twos_complement(-x_int, n) # [|X|]补 neg_X_tc = X # [-X]补 就是 [X]补 本身？不对，[-X]补 是 -x_int 的补码。 # 更准确：[-X]补 = [ - (负数) ]补 = [正数]补 neg_X_tc = to_twos_complement(-x_int, n) MQ = Y if sign_y == 0 else (Y & ((1 << (n-1)) - 1)) # 如果Y为负，运算时取数值部分（去掉符号位） count = n - 1 # 只对数值部分进行n-1次循环 print(f"乘数符号 sign_y = {sign_y}") if sign_y == 1: print(f"乘数为负，运算过程使用 |Y| = {MQ:0{n-1}b} (数值部分)，被乘数使用 [|X|]补 = {X_mag_tc:0{n}b}") print(f"校正项为 [-X]补 = {neg_X_tc:0{n}b}") else: print(f"乘数为正，运算过程直接使用 [Y]补 和 [X]补") print(f"初始化: P={P:0{n}b}, MQ(运算部分)={MQ:0{n-1}b}, count={count}") # 主循环（对数值部分进行） for i in range(count): lsb = MQ & 1 print(f"\n[步骤 {i+1}] MQ(运算)最低位 = {lsb}") if lsb == 1: P = (P + X_mag_tc) & ((1 << n) - 1) # 取低n位，模拟n位加法器 print(f" 执行 P + [|X|]补: {P-X_mag_tc:0{n}b} + {X_mag_tc:0{n}b} = {P:0{n}b}") # 右移 (算术右移，对于补码，P是补码，高位补符号位) # 将P和MQ联合右移 sign_bit_p = (P >> (n-1)) & 1 combined = (P << (n-1)) | MQ combined = (combined >> 1) | (sign_bit_p << (2*n-2)) # 算术右移，高位补P的符号位 P = combined >> (n-1) MQ = combined & ((1 << (n-1)) - 1) print(f" 算术右移后: P={P:0{n}b}, MQ(运算)={MQ:0{n-1}b}") # 校正步骤 if sign_y == 1: print(f"\n乘数为负，执行校正: P = P + [-X]补") P = (P + neg_X_tc) & ((1 << n) - 1) print(f" 校正后 P = {P:0{n}b}") # 组合最终乘积的补码 [P, MQ] (高位在前) product_tc = (P << (n-1)) | MQ # 将补码转换回十进制整数 def from_twos_complement(val, bits): if (val >> (bits-1)) & 1: # 符号位为1，是负数 return val - (1 << bits) else: return val final_product = from_twos_complement(product_tc, 2*n-1) # 乘积位宽为 2n-1 位？ # 更准确地说，n位乘n位，乘积最多2n位。我们这里用了n位P和n-1位MQ，组合成2n-1位，还差1位符号位？实际上P已经包含了符号位。 # 简化处理：我们的P是n位补码，MQ是n-1位数值，组合成 (n + n-1) = 2n-1 位，最高位是P的符号位。 # 所以乘积的补码总位宽是 2n-1 位。 print(f"\n运算结束。") print(f"乘积的补码表示: {product_tc:0{2*n-1}b}") print(f"最终乘积（十进制）: {final_product}") return final_product # 测试 print("="*50) twos_complement_corrective_multiply(3, 5, n=4) # 3 * 5 = 15 print("="*50) twos_complement_corrective_multiply(3, -5, n=4) # 3 * (-5) = -15 ``` 校正法虽然实现了补码乘法，但它的流程不够统一，需要根据乘数的符号进行分支判断。有没有一种方法，能用一个完全统一的、无需校正的流程来处理所有情况呢？这就是接下来要介绍的、更为强大的Booth算法。 ## 4. 效率与统一的典范：Booth算法详解与模拟 Booth算法（有时也称为比较法或Booth's multiplication algorithm）是补码乘法领域的一个里程碑。它最大的优势在于**流程统一**，无论乘数是正、负还是0，都使用完全相同的操作步骤。此外，它还能**识别并跳过连续的1或连续的0**，从而在某些情况下减少加法操作的次数，提升效率。其核心在于**检查乘数相邻两位的变化**，而不是只看单独一位。 Booth算法的规则基于乘数寄存器 `MQ`，并引入一个附加位 `MQ_{-1}`，初始为0。在每一步中，我们查看 `(MQ_0, MQ_{-1})` 这个两位组合： * **`(0, 0)` 或 `(1, 1)`**：意味着连续0或连续1，执行**算术右移**操作。 * **`(0, 1)`**：意味着从1变到0（即一串1的结束），执行 **`P = P + [X]补`**，然后右移。 * **`(1, 0)`**：意味着从0变到1（即一串1的开始），执行 **`P = P + [-X]补`**，然后右移。 算法结束后，`(P, MQ)` 中的内容就是乘积的补码。 为什么这样是有效的？直观理解：在二进制中，一串连续的1可以转化为一个更高效的计算。例如 `0011110` 可以看作 `0100000 - 0000010`。Booth算法通过检测“从0到1”和“从1到0”的边界，自动完成这种转换。 让我们来实现它。这次，我们将构建一个非常清晰、每一步都打印关键状态的Booth算法模拟器。 ```python def booth_algorithm(x_int, y_int, n=4): """ Booth算法（比较法）实现。 """ # 转换为n位补码 def to_tc(val, bits): mask = (1 << bits) - 1 if val >= 0: return val & mask else: return ((1 << bits) + val) & mask def from_tc(val, bits): if (val >> (bits-1)) & 1: return val - (1 << bits) else: return val X_tc = to_tc(x_int, n) Y_tc = to_tc(y_int, n) neg_X_tc = to_tc(-x_int, n) # 计算 [-X]补 print(f"\n开始Booth算法: {x_int} * {y_int}") print(f"[X]补 = {X_tc:0{n}b}, [Y]补 = {Y_tc:0{n}b}, [-X]补 = {neg_X_tc:0{n}b}") # 初始化寄存器 # P 扩展1位符号位，用于正确处理加法溢出（双符号位思想简化） P = 0 # 我们可以认为P是n+1位，最高位是符号位，但这里用n位模拟，小心溢出 MQ = Y_tc MQ_minus1 = 0 # 附加位 count = n # 为了更稳定，使用更宽的位宽进行中间计算 P_extended = 0 # 扩展位宽，例如n+1位 print(f"初始化: P={P:0{n}b}, MQ={MQ:0{n}b}, MQ_-1={MQ_minus1}, count={count}") print("规则: (MQ0, MQ_-1) -> 操作") print(" 00或11 -> 仅右移") print(" 01 -> P + [X]补, 右移") print(" 10 -> P + [-X]补, 右移") for i in range(count): mq0 = MQ & 1 pair = (mq0, MQ_minus1) print(f"\n--- 第 {i+1} 轮循环 ---") print(f" 检查 (MQ0, MQ_-1) = ({mq0}, {MQ_minus1})") old_P = P operation = "" if pair == (0, 0) or pair == (1, 1): operation = "仅右移" elif pair == (0, 1): # P + [X]补 P = (P + X_tc) & ((1 << n) - 1) operation = f"P + [X]补: {old_P:0{n}b} + {X_tc:0{n}b} = {P:0{n}b}" elif pair == (1, 0): # P + [-X]补 P = (P + neg_X_tc) & ((1 << n) - 1) operation = f"P + [-X]补: {old_P:0{n}b} + {neg_X_tc:0{n}b} = {P:0{n}b}" print(f" 操作: {operation}") # 算术右移 (P, MQ, MQ_-1) # 1. 确定右移后P的最高位（符号位） sign_bit_p = (P >> (n-1)) & 1 # 2. 将P和MQ组合，并考虑MQ_-1 # 组合体： P (n位) + MQ (n位) + MQ_-1 (1位) -> 总共2n+1位 # 右移时，P的最低位进入MQ最高位，MQ的最低位进入MQ_-1，MQ_-1丢弃 # 简单实现：分别处理 new_MQ_minus1 = MQ & 1 # 当前MQ的最低位成为新的MQ_-1 # MQ右移，其高位由P的最低位填充 bit_from_P = P & 1 MQ = (MQ >> 1) | (bit_from_P << (n-1)) # P算术右移，高位补其原来的符号位 P = (P >> 1) | (sign_bit_p << (n-1)) MQ_minus1 = new_MQ_minus1 print(f" 算术右移后: P={P:0{n}b}, MQ={MQ:0{n}b}, MQ_-1={MQ_minus1}") # 组合结果：乘积的补码在 (P, MQ) 中 # 注意：P是n位，MQ是n位，但通常乘积是2n位，P是高位，MQ是低位。 # 但我们的P在运算中可能不是完整的2n位中的高n位，因为初始为0且右移了n次。 # 实际上，经过n次右移后，原始的P（高位部分）和MQ（低位部分）已经正确组合。 # 乘积的补码是 P和MQ的连接吗？需要仔细分析。 # 在标准描述中，最终结果是 (P, MQ)，其中P和MQ都是n位。 product_tc_combined = (P << n) | MQ # 但这样得到的是2n位数，其最高位是P的最高位。 # 我们需要将其解释为2n位的补码。 final_product = from_tc(product_tc_combined, 2*n) print(f"\n算法结束。") print(f"最终寄存器状态: P={P:0{n}b}, MQ={MQ:0{n}b}") print(f"乘积补码 (P,MQ组合): {product_tc_combined:0{2*n}b}") print(f"最终乘积（十进制）: {final_product}") return final_product # 测试Booth算法 print("="*50) booth_algorithm(3, 5, n=4) # 3 * 5 = 15 print("="*50) booth_algorithm(3, -5, n=4) # 3 * (-5) = -15 print("="*50) booth_algorithm(-3, -5, n=4) # (-3) * (-5) = 15 ``` 运行这段代码，你可以观察到Booth算法如何通过检查两位组合来统一决定操作。对于 `3 * 5` (`0011 * 0101`)，乘数 `0101` 中有一段 `01` 和 `10` 的变化，算法会相应地执行加 `[X]补` 和加 `[-X]补`。而对于 `3 * -5` (`0011 * 1011`)，算法依然按照同样的规则运行，最终得到正确的结果。 ## 5. 算法对比与实战应用场景分析 现在，我们已经拥有了三种乘法算法的完整Python实现。是时候将它们放在一起，从多个维度进行对比，并探讨它们各自的应用场景和启发。 为了更直观地对比，我们设计一个测试，用相同的输入运行三种算法（原码乘法需输入绝对值或正数），并观察其过程和结果。 ```python def compare_algorithms(x, y, n=4): """对比三种乘法算法""" print("="*60) print(f"算法对比测试: {x} * {y} (位宽={n})") print("="*60) # 原码乘法（输入绝对值） print("\n1. 原码一位乘法（带符号）:") res1 = signed_magnitude_one_bit_multiply(x, y, n) # 补码校正法 print("\n2. 补码一位乘法（校正法）:") res2 = twos_complement_corrective_multiply(x, y, n) # Booth算法 print("\n3. Booth算法（比较法）:") res3 = booth_algorithm(x, y, n) print("\n" + "="*60) print("总结对比:") print(f" 数学正确结果: {x * y}") print(f" 原码乘法结果: {res1} {'✓' if res1 == x*y else '✗'}") print(f" 补码校正法结果: {res2} {'✓' if res2 == x*y else '✗'}") print(f" Booth算法结果: {res3} {'✓' if res3 == x*y else '✗'}") # 运行对比测试 compare_algorithms(3, 5, n=4) compare_algorithms(-3, 5, n=4) ``` 通过对比测试和之前的实现，我们可以总结出以下关键点： * **设计哲学与硬件亲和度**： * **原码一位乘** 最直观，与人类计算思维最接近，但需要独立的符号处理电路。在早期硬件或某些专用场景（如浮点数尾数计算，其本身是原码）中仍有价值。 * **补码校正法** 是向统一补码运算迈进的一步，但校正步骤破坏了流程的一致性，增加了控制复杂度。 * **Booth算法** 实现了真正的流程统一，其“检查相邻位”的逻辑可以用一个简单的状态机实现，非常适合硬件流水线设计。它代表了工程上对“优雅”和“高效”的追求。 * **性能考量**： * 在最坏情况下，三种算法都需要进行 `n` 次加法（或潜在加法）和 `n` 次移位。 * 但在**平均情况**或遇到特定数据模式时，Booth算法有可能减少加法次数。例如，乘数中包含大段连续的 `1` 时，Booth算法能将其转换为一次加和一次减，从而节省操作。 * **现代应用**： * 在现代CPU的ALU中，直接使用这种逐位迭代算法的场景已经不多。为了追求极致性能，工程师们设计了诸如**华莱士树（Wallace Tree）**、**布斯编码（Booth Encoding）与部分积压缩**、**并行乘法器**等更高级、更并行的结构。 * 然而，Booth算法的思想——**通过编码减少部分积的数量**——仍然是这些高速乘法器设计的核心基础之一。理解Booth算法，是理解这些更复杂优化技术的敲门砖。 * **对我们的启发**： * **从软件看硬件**：这次编码实践最宝贵的收获，是建立了软件思维与硬件设计之间的桥梁。当你用 `if-else` 判断乘数末位，用 `>>` 和 `<<` 模拟移位时，你就在模拟硬件中的控制逻辑和数据通路。 * **抽象的力量**：Booth算法通过巧妙的规则抽象，掩盖了正负数处理的复杂性。这提醒我们，好的算法设计往往在于找到一个更高层次的视角，将特殊情况统一到一般流程中。 * **理解“为什么”**：我们不仅知道了算法“怎么做”，更通过代码的拆解，理解了它们“为什么”要这么做——都是为了适应硬件的约束（有限的寄存器、简单的加法器、对统一流程的需求）。 写完这些代码并看到它们正确运行后，我最大的体会是，很多底层原理一旦动手实现过，印象就会深刻得多。下次当你看到CPU的乘法指令时，脑海里或许就能浮现出这些寄存器在时钟驱动下不断“加-移”的画面。这种从抽象理论到具象模拟的跨越，正是学习计算机组成原理最有趣的环节。