企业官网建设流程全解析

简介：面向计算机组成原理学习者的Booth算法C语言实现源码包，通过简洁代码演示补码乘法中与逐位累加不同的优化思路，适合课程实验、课后研读及微处理器乘法单元设计参考。压缩包共14个文件、184KB，主要包含cpp源文件、VC6.0的dsw/dsp工程文件、可直接运行的exe、pch预编译头、obj目标文件以及pdb调试信息等，还附有一份doc文档辅助理解。已有455人学习下载。算法实现覆盖位扩展、符号调整、部分积计算与最终累加，读者可在VC6.0中单步跟踪变量变化，直观观察每一步是加法还是减法；也可以修改乘数位宽，验证算法对不同长度二进制数的适应性。整体文件结构精简，能帮助把课本上的Booth算法原理落地为可编译、可观察、可扩展的C程序，并为后续学习硬件乘法器设计打下基础。 如果你正在学“计算机组成原理”，特别是准备课程设计里的乘法器实验，那你大概率已经背过Booth算法的规则：Q0和Q-1是00就直接右移，01加M，10减M，11也直接右移。规则背得滚瓜烂熟，但一到自己动手写C代码就懵了——A寄存器到底用int还是long？Q为什么不能随随便便用一个int？所谓的“组合右移”是不是真的要把几个变量拼成一个64位整数再移位？最后乘积又要怎么拿回来？这篇文章我把Booth算法的原理、C源码实现和调试心得一次讲透，给你一份可以直接跑通的参考实现，顺带帮你避开我当年踩过的坑。

1. 为什么计算机组成原理课程离不开Booth算法

1.1 补码乘法的第一道坎：符号位不能直接参与运算

计算机里整数普遍用补码存储，这让加法和减法变得特别舒服，一个加法器通吃正负。但到了乘法这里，补码就暴露问题了：直接按十进制竖式的思路做乘法时，如果乘数是负数，最高位那个符号位1会被当成数值参与运算，结果必然是错的。

最简单的改进办法是先判断符号，取绝对值转成无符号乘法，最后再根据符号位补一个负号。这在逻辑上没有毛病，可硬件实现起来要多一套“绝对值转换+符号判断”的电路，而且在有符号和无符号之间来回切换，延迟和面积都不占优。Booth算法的价值恰恰在于：不需要预先处理符号，直接在补码上做乘法，符号位在运算过程中自然地处理掉。这也是为什么许多教学级处理器（比如MIPS、RISC-V的简化模型）里，讲解乘法器时总会专门提Booth算法。

1.2 Booth算法是怎么做到“带着符号乘”的

Booth算法的核心视角很有意思：别死盯着乘数的每一位去“累加”，而是观察乘数里相邻两位之间的关系。补码表示里经常出现大段的连续0和连续1，而一段连续的1，在数学上等价于“一次高位减法、一次低位加法”。

举个例子，二进制00111000中间那一串111，可以写成01000000减去00001000。对乘法来说，与其对着三个1做三次加法，不如在这一段连续1的开头减一次、结尾加一次。这样不仅减少了部分积的数量，还能天然兼容补码的符号位。

当然，这是一种宏观理解。真正落地时，Booth算法每一轮只根据乘数最低位Q0和它右侧的附加位Q-1决定动作，规则非常简单。所以在不少高校的计算机组成原理课程设计里，Booth算法被当成“preproject”级别的热身题：要求用C或Verilog实现4位或8位补码乘法器，方便后续接入模拟器或实验板。写C版本的意义不只是应付作业，它帮你把寄存器、时钟周期、数据通路的抽象概念，真正落到变量和循环里。

1.3 一篇博客能帮你拿到什么

这篇博客的目标很简单：先讲清楚Booth算法为什么是那四条规则，再给出一个不依赖编译器奇技淫巧的C源码，最后把调试时最容易踩的坑列出来。无论你是刚学组成原理的大学生，还是准备面试时复习计算机体系结构的开发者，这份源码和思路都可以直接参考。

2. Booth算法原理：一张规则表的背后

2.1 硬件视角的寄存器配置

先看硬件乘法器的基本结构。要实现n位补码乘法，通常需要这几个部件：

• M寄存器：n位，存放被乘数；
• Q寄存器：n位，存放乘数；
• A寄存器：n+1位，累加器，用来暂存高位部分积；
• Q-1寄存器：1位，附加位，挂在Q最低位右侧。

初始化时A=0，Q放乘数，Q-1=0。每一轮先看Q0和Q-1的组合决定操作，然后把整个(A,Q,Q-1)拼起来做一次算术右移。重复n次后，(A,Q)拼接出来的就是2n位乘积。

这个过程可以用一个很形象的比喻：A和Q拼在一起像一条传送带，每轮先看传送带最右侧两位的状态，决定在A上加M、减M还是不动，然后整条传送带右移一格。Q-1就是传送带滑过去之后留下的那个“脚印”。

2.2 四条规则一张表

规则本身相当简单：

也就是说，每一轮真正需要动加法器的只有两种情况：01加一次，10减一次。00和11都是“光右移、不动手”。

2.3 为什么01要加、10要减

这背后是一个简洁的数学恒等式。设乘数Y的n位补码为y_{n-1}y_{n-2}...y_0，并规定y_{-1}=0，那么补码的值可以写成：

Y = -y_{n-1} * 2^(n-1) + Σ_{i=0}^{n-2} y_i * 2^i

通过整理，可以得到等价形式：

Y = Σ_{i=0}^{n-1} (y_{i-1} - y_i) * 2^i

意思是：每一位对乘积的贡献，取决于当前位y_i和前一位y_{i-1}的差值。当出现0→1跳变时，差值为+1，说明这一位是一段连续1的开头，需要把被乘数加到这个位置上；当出现1→0跳变时，差值为-1，说明一段连续1结束，需要把被乘数减掉。而00和11差值为0，不做操作。

不用数学公式的话，可以这样理解：补码里的符号位也是“位”的一部分，连续1这一段被看作“高位加一、低位减一”的组合。Booth算法每一步都在修正这个差值，符号位自然就在运算中被消化了。

2.4 为什么每一步都必须算术右移

这里有个关键动作：每一次操作后都要做“算术右移”，而不是普通右移。算术右移会保持最高位符号位不变，相当于对补码做一次除以2的操作。

A中保存的是高位部分积，Q中保存的是低位部分积。如果采用逻辑右移，负数补码右移后最高位补0，符号位没了，高位部分积就会乱套。所以“算术右移”不是可选项，而是补码运算的必然要求。在用C模拟时，这一点尤其容易踩坑，后面会详细说。

3. C语言源码实现：把寄存器搬进变量

3.1 类型选择：int、uint32_t和比特掩码

写C版本的第一步，是决定每个寄存器用什么类型模拟。我的选择是：

• A和M用int32_t。因为A要支持负数累加，而且要利用算术右移保持符号位，所以必须是有符号类型；
• Q用uint32_t。因为Q在算法里只做无符号右移和位拼接，如果用了有符号int，右移时最高位会塞符号位，结果必然错误；
• Q-1用一个普通int变量，只要存0或1即可；
• 所有“只取低bits位”的地方，统一用掩码处理。

还有一点容易被忽略：M在参与运算前，一定要先截断成bits位补码并做符号扩展。否则，如果调用方传入的整数本身带了高位垃圾，A+M和A-M就会混进不该有的高位信息，结果在最高位处会出错。我用了一个truncate_to_bits函数来做这件事。

3.2 核心循环和“组合右移”的正确拆解

最核心的是每一轮结尾的那个组合右移。硬件里(A,Q,Q-1)是一整个移位寄存器，但在C语言里，它们只是几个独立变量。正确拆解方式如下：

1. 先保存旧的Q0，它将成为新的Q-1；
2. 再保存A的最低位，它要移入Q的最高位；
3. A自己右移一位，保持符号位不变；
4. Q右移一位，并把刚才保存的A最低位移到Q的最高位。

这里最常犯的错误是把A、Q分别独立右移了事，结果Q最高位补了一个0，整体拼接就断了。记住：A的最低位必须进入Q的最高位，Q的最低位必须进入Q-1，三者是连通的。

3.3 完整可运行源码

下面这个实现以4位或8位补码乘法为例，bits参数控制位宽。代码已经在主流编译器上验证过，可以直接跑：

#include <stdio.h> #include <stdint.h> // 将 value 按 bits 位补码截断，并符号扩展为 int static int truncate_to_bits(int value, int bits) { int mask = (1 << bits) - 1; int v = value & mask; if (v & (1 << (bits - 1))) { v |= ~mask; } return v; } // Booth 一位乘法，bits 表示补码位宽 int booth_multiply(int multiplicand, int multiplier, int bits) { int32_t A = 0; // 累加器，硬件上为 bits+1 位 uint32_t Q = (uint32_t)multiplier & ((1u << bits) - 1); // 乘数寄存器 int32_t M = truncate_to_bits(multiplicand, bits); // 被乘数寄存器 int Q_1 = 0; // 附加位 int result_mask = (1 << bits) - 1; for (int i = 0; i < bits; i++) { int q0 = Q & 1; if (q0 == 0 && Q_1 == 1) { A = A + M; // 01：加法 } else if (q0 == 1 && Q_1 == 0) { A = A - M; // 10：减法 } // 00 / 11：不操作 // 组合算术右移 (A, Q, Q-1) >>> 1 Q_1 = q0; // 旧 Q0 变成新 Q-1 uint32_t a_lsb = (uint32_t)A & 1u; // A 的最低位 A >>= 1; // A 算术右移，符号位保持 Q = (Q >> 1) | (a_lsb << (bits - 1)); // A 最低位移入 Q 最高位 } // 拼接结果：A 的低 bits 位为高半部分，Q 为低半部分 uint32_t product = (((uint32_t)A & (uint32_t)result_mask) << bits) | ((uint32_t)Q & (uint32_t)result_mask); // 将 2*bits 位补码转换成 int if (product & (1u << (2 * bits - 1))) { return (int)(product | ~((1u << (2 * bits)) - 1)); } return (int)product; } int main(void) { printf("%d\n", booth_multiply(-2, -3, 4)); // 6 printf("%d\n", booth_multiply(7, -3, 4)); // -21 printf("%d\n", booth_multiply(-7, -3, 4)); // 21 printf("%d\n", booth_multiply(5, 5, 4)); // 25 return 0; }

代码里有两个地方需要额外说明。第一，A是用int32_t模拟的，它的物理位宽远大于bits+1，但通过M的截断和每次右移的符号扩展，A有效位始终被限制在bits+1位补码语义内，所以高位多余符号扩展位不会影响正确性。第二，最后拼接乘积时，必须先把A的低bits位和Q的低bits位拼成一个2*bits位的无符号数，再统一判断正负并转换回int。如果提前对A做符号扩展，会把A的符号位错误地带进乘积。

3.4 手算验证两个经典用例

源码能跑是一回事，能看懂为什么对是另一回事。这里用手算方式验证两个典型case。

第一个：M=-2，Q=-3，4位补码，正确结果是6。初始化A=0，Q=1101（无符号13），Q-1=0。四轮循环的状态变化如下：

最终A=0，Q=0110，乘积为6，正确。

第二个：M=7，Q=-3，4位补码，正确结果是-21。最终A=-2（二进制1110），Q=1011，拼起来是11101011，按8位补码解释就是-21，也对。

这里能看到一个很有意思的现象：4位操作数相乘，结果需要8位才能表示。A寄存器虽然名义上是bits+1位，但最终真正参与结果拼接的只是A的低bits位。硬件上A多出的那一位符号扩展位，只负责在中间过程中撑住符号，不进最终乘积。

4. 实操中的坑和调试技巧

4.1 第一个坑：有符号数右移不一定是算术右移

我用了A >>= 1来实现算术右移，但在C语言标准里，有符号负数的右移是实现定义行为。也就是说，标准没有强制规定编译器必须做算术右移。不过在实际环境中，GCC、Clang、MSVC对所有主流平台都会生成带符号扩展的算术右移指令，所以在绝大多数场景下可以直接用。

如果你写的代码要在特别严格的嵌入式环境或跨编译器测试，可以自己写一个强制算术右移的函数：先把有符号数转成无符号，右移后手动恢复符号位。比如：

int32_t sar32(int32_t x, int shift) { if (x >= 0) return x >> shift; return ~((~(uint32_t)x) >> shift); }

但说实话，课程设计和日常工作里直接用>>就够了，只要知道有这个边界即可。

4.2 第二个坑：Q寄存器千万别用有符号类型

这是我当年调试最久的一个问题。如果把Q定义成int，右移时最高位会用符号位补齐，等于给乘数寄存器加了一个不受控制的符号扩展机制。小数值正正相乘时可能看不出来，一旦遇到负数，每一位的移位都会把高位污染，最终乘积错得离谱。

解决方案很简单：Q用uint32_t。因为Q在整个算法中只需要无符号右移和位拼接，没有任何需要符号扩展的语义。使用时再按需取低bits位即可。

4.3 第三个坑：结果拼接前不要提前“人工符号扩展”

有些同学会在循环结束后直接把A的低位接到结果里，然后看到A是负数就立刻对整个乘积做符号扩展，结果反而出错。正确做法是：先把A的低bits位和Q的低bits位拼成一个完整的2*bits位无符号数，然后看这个无符号数的最高位，统一判断是正是负，再转回有符号int。顺序反了，符号位就找错了位置。

4.4 多写几个边界用例再提交

验证Booth算法，千万别只测正正相乘。至少要把这些组合都跑一遍：

其中-8在4位补码里是1000，7是0111，乘积-56需要8位补码表示，能测到符号扩展在高位的正确处理。

4.5 从4位改到8位、16位，要注意什么

把代码里的bits从4改成8很容易，但如果要扩展到16位，需要留意两件事。一是掩码和移位宽度：1 << bits在bits等于32时是未定义行为，建议中间统一用uint64_t做拼接运算。二是打印调试时，A和Q要按十六进制看，别再按十进制看——十进制值在符号扩展后会让人怀疑人生。

如果你做课程设计，还可以在这个源码基础上加一个“中间过程打印”开关，每轮输出A、Q、Q-1的二进制串，对照你手算的表格，一眼就能定位是哪一轮的加减或右移出了问题。这个习惯比任何调试器都管用。

最后分享一个我自己的体会。Booth算法本身不难，难的是在模拟硬件时序时别让C语言的类型特性渗进来。Q用了有符号int、M没有提前截断、结果拼接时符号扩展顺序搞反，这三个坑几乎每个人都至少踩一个。希望上面的源码和避坑记录，能让你少花几个通宵。

本文还有配套的精品资源，点击获取