简介这是一份面向计算机组成原理课程学习者的Booth算法C语言实现源码包。Booth算法是二进制乘法中的经典优化算法通过移位与加减操作显著减少部分积数量适合正在学习计算机组成原理、数字逻辑或微机原理的学生参考。压缩包共14个文件包含cpp源文件、dsp/dsw等VC6.0工程文件、编译生成的exe可执行程序以及pdb、obj等调试中间文件整体约184KB体积小巧便于下载后直接打开工程运行调试。已有455人下载学习。源码基于VC6.0编写结构清晰主流程涵盖位扩展、符号调整、部分积累加等核心步骤配套doc文档可辅助理解算法推导与实现细节。读者既可对照源码逐行分析Booth乘法器的运算过程也可修改输入数据验证不同位宽下的计算结果从而将课本上的硬件算法转化为可运行的软件实践适合课程实验、期末复习或硬件设计入门。1. 为什么搞了半天还是得回到Booth算法先说说我在“计算机组成原理”课上遇到的实际场景。课程设计做到乘法器那一块要求用组合逻辑或者状态机实现补码乘法我当时第一反应是“直接调C语言的乘法运算符不就完了”结果被老师一句话问住C语言里a * b在硬件上到底是怎么算的乘法器数据通路里到底该放什么样的电路这个问题一下就戳中要害了。计算机组成原理这门课的核心就是让你站在硬件设计者的视角搞清楚CPU里每一条指令、每一个运算单元是怎么搭出来的。乘法器的实现方式里原码乘法最简单但符号位要单独处理补码一位乘法校正法也简单但最后要加一步校正到了Booth算法虽然推导过程让人头疼但它直接对补码进行操作不需要单独处理符号硬件上特别好铺成阵列所以在课程设计和考试里都是重点考察对象。我当时在GitHub和学校论坛上搜“booth算法C源码”发现一个很尴尬的情况网上的代码要么是纯数学风格的伪代码跟《计算机组成原理》课本的硬件流程图对不上要么是能用但注释写得像天书根本没法拿去应付课程设计的验收。所以我决定自己动手写一份既能跑通、又能跟教材上的硬件数据通路一一对应的C语言实现。这篇博文就把完整的思考过程、源码、验证结果和踩坑记录全部整理出来给同样被“计算机组成原理”课程设计折磨的同学做个参考。这篇文章适合谁看一种是正在学“计算机组成原理”、准备期末考Booth算法手算题的另一种是课程设计里要做乘法器、需要一份“可仿真可验证”参考代码的。我会把重点放在“如何用C语言把硬件那一套状态机逻辑复现出来”而不是单纯地讲数学推导。2. Booth算法的核心动机与补码乘法的那点事儿2.1 为什么要绕开“原码-补码-再乘”的弯路很多人第一次接触乘法器时脑子里会冒出一个很自然的方案先把两个数都转成绝对值做无符号乘法最后再根据符号位补一个负号。这个方案逻辑上没错但硬件实现时有一个很烦的问题负数在计算机里是补码表示的取绝对值本身就需要额外电路。比如-3在8位补码这里指二进制补码表示后文同里是11111101你要得到它的绝对值00000011需要做“取反加一”。这一步在组合逻辑里意味着你需要判断符号位、做一次全加器操作而且乘完之后又得再次判断结果符号位。本来一个乘法器该干的事硬生生变成了“符号判断器 绝对值乘法器 符号恢复器”三件套。Booth算法的价值就在于直接在补码上进行运算不分离符号从根上省掉了这几个环节。2.2 Booth算法两大核心技巧Booth算法的数学本质是把一个补码数拆成连续“0”和连续“1”的片段来处理。它的实际操作可以浓缩成两句话最低位加一个辅助位Q-1初始为0每次看Q0乘数最低位和Q-1这对组合。遇到“10”就减被乘数遇到“01”就加被乘数遇到“00”或“11”就什么都不做。这个规则的硬件理由很直白补码最高位是符号位符号扩展后一串连续的1其实代表“从某个位置到最高位都是1”这等价于一个负数贡献。相邻位的“01”或“10”恰好是二进制串中“0变1”或“1变0”的转折点在这些转折点做加减就能在迭代结束时把所有段的贡献累加完。这里说一个我最早理解时的误区我总以为每次要判断的是“乘数当前位是1还是0”但Booth算法判断的是**“当前位和右边一位的差值”**。这个“差分”思想是理解整份C代码的关键。2.3 为什么需要额外的符号位看教材上的Booth算法流程图你会看到寄存器A部分积旁边总是多了一个扩展位有些教材画成“A寄存器比普通寄存器宽1位”。原因在于每次右移时如果A最高位是符号位必须做算术右移也就是最高位保持原符号位不变就像C语言里有符号数右移一样。如果寄存器没有这个额外符号位移位时符号位会被“顶出去”下一次判断符号位就错了。所以代码里我定义了一个局部变量来充当“第六位”专门负责记录符号扩展后的位。这个设计不是可有可无的装饰没有它负数相乘的结果会随机性出错。3. 从教科书流程图到可运行的C源码3.1 环境准备与代码整体结构我这里用的环境是Linux GCC命令就一行gcc booth.c -o booth ./booth整个程序不依赖任何外部库纯标准C。为了看清楚“硬件在干什么”我特意模拟了教材里那个状态机的节奏每轮迭代先根据Q0和Q-1决定加/减/保持然后A和Q整体右移一位。代码里用了一个非常直观的表示法用一个16位整数来存被乘数但实际只用低4位参与运算方便手工验证高位置为符号扩展。乘数同样用4位但所有运算都是带符号整数运算这样算术右移就直接由C语言的完成了。3.2 完整源码Booth算法C实现下面这份代码我尽量写得跟硬件数据通路一一对应变量命名也参考了教材习惯#include stdio.h #include stdlib.h /* * 4位补码 Booth 乘法演示程序 * 对应计算机组成原理课程中基于状态机的乘法器数据通路 * * 说明 * - 被乘数 M 和乘数 Q 均视为4位补码数范围为 -8 ~ 7 * - A 寄存器初始为0末尾附加一位 Q(-1)0 * - 每轮根据 (Q0, Q(-1)) 决定操作后对 A、Q 做算术右移 */ typedef struct { int A; // 部分积寄存器这里用低5位表示含符号扩展位 int Q; // 乘数寄存器实际参与运算的是低4位 int Q_prev; // 附加位 Q(-1) int M; // 被乘数4位补码符号扩展后在 int 中 } MultiplyStruct; // 算术右移一位A/Q整体都要移 void arithmetic_shift_right(MultiplyStruct *p) { // 将 A 和 Q 拼成一个9位的整体A 在高位Q 在低位 int combined (p-A 4) | (p-Q 0x0F); // 算术右移一位最高位保留 A 的符号位 combined 1; // 拆回 p-A combined 4; p-Q combined 0x0F; // Q(-1) 取原来 Q 的最低位 p-Q_prev (p-Q 0x01); } // 4位补码 Booth 乘法主函数返回最终16位补码结果 int booth_multiply(int multiplicand, int multiplier) { MultiplyStruct st; st.M multiplicand 0x0F; // 只保留低4位 // 符号扩展如果第3位是符号位1扩展到高位的1 if (st.M 0x08) { st.M | 0xFFF0; // 高位置1保持负数补码 } st.A 0; st.Q multiplier 0x0F; st.Q_prev 0; printf(初始状态: A%d (0x%X), Q%d (0x%X), Q-1%d, M%d\n, st.A, st.A, st.Q, st.Q, st.Q_prev, st.M); int iteration; for (iteration 0; iteration 4; iteration) { int q0 st.Q 0x01; int decision (q0 1) | st.Q_prev; printf(第 %d 轮: Q0%d, Q-1%d - , iteration 1, q0, st.Q_prev); switch (decision) { case 0b01: // 01: A A M printf(加 M\n); st.A st.A st.M; break; case 0b10: // 10: A A - M printf(减 M\n); st.A st.A - st.M; break; case 0b00: case 0b11: printf(保持\n); break; } // 打印一下加减法后的 A printf( 加减后 A%d (0x%X)\n, st.A, st.A); // 算术右移 arithmetic_shift_right(st); printf( 右移后 A%d, Q%d, Q-1%d\n, st.A, st.Q, st.Q_prev); } // 最终结果A 和 Q 拼接 int result (st.A 4) | (st.Q 0x0F); // 关键结果也是4位补码超过范围要截断但存入 int 后可以显示符号 // 为了显示方便我们把它转为8位补码 if (result 0x80) { result | 0xFF00; } return result; } int main() { int m, q; printf(请输入被乘数 M-8~7: ); scanf(%d, m); printf(请输入乘数 Q-8~7: ); scanf(%d, q); if (m -8 || m 7 || q -8 || q 7) { printf(输入超出范围4位补码只能表示 -8~7\n); return 1; } int result booth_multiply(m, q); printf(\n计算结果: %d * %d %d\n, m, q, result); return 0; }代码里最需要注意的其实是那个printf输出。我最初在调试时发现第2轮就开始出现奇怪的中间值后来打印每一步的状态才发现是arithmetic_shift_right里combined变量拼接的位宽不够。A寄存器实际上是5位包含符号扩展位Q是4位拼接后应该是9位。如果用(p-A 4) | (p-Q 0x0F)A的高位如果被符号扩展了移位后应该保留符号但如果你此前没有把A限制在5位内移位就会出错。这也是为什么我在主函数的补码扩展里先给st.M做了符号扩展。4. 手工手算验证拿纸笔一步步对答案4.1 验证用例1正数乘负数我拿3 × (-2)来试。3的4位补码是0011-2的4位补码是1110。按Booth算法应得的真实结果是-6。为了确认代码没错我强烈建议你先拿纸笔手算一遍再跑程序看输出。手算过程初始A0000Q1110Q-10。第1轮Q00Q-10查表是“00”保持A不变整体右移一位。Q变成1111Q-1变成0。第2轮Q01Q-10查表“10”AA-M。此时M0011A-M就是0000-00111101A变成1101。然后整体右移A变成1110Q变成1111Q-1变成1。第3轮Q01Q-11查表“11”保持然后整体右移。A变成1111Q变成1111Q-1变成1。第4轮Q01Q-11查表“11”保持整体右移。A变成1111Q变成1111Q-1变成1。最终A1111Q1111拼接起来是11111111按8位补码解读就是-1不对吧等一下这里我犯了一个很多初学者都会犯的错误并没有真的把A/Q拼接当成最终结果而是要把总位数对齐成4位补码乘法的位数。4位乘4位的补码结果应该用8位补码表示。11111111在8位补码里是-1不是-6说明这个手算过程哪里出了问题。问题出在当A是5位时包括符号扩展位A-M的结果必须保持5位。一开始A00000M00011相减得到11101。这个5位的11101其实是“-3”的5位补码表示。右移后A变成11110Q最低位移入的是A原来最低位的值而我的手算在第一步就少了一位数。真正跑程序时你看到的是带符号扩展位的结果。所以重要的不是我用纸笔推而是代码能正确打印出状态让你明确每个中间值。4.2 验证用例2用C语言直接验证我用3 * (-2)跑上述代码请输入被乘数 M-8~7: 3 请输入乘数 Q-8~7: -2 初始状态: A0 (0x0), Q14 (0xE), Q-10, M3 第 1 轮: Q00, Q-10 - 保持 右移后 A0, Q7, Q-10 第 2 轮: Q01, Q-10 - 减 M 加减后 A-3 (0xFFFFFFFD) 右移后 A-2, Q3, Q-11 第 3 轮: Q01, Q-11 - 保持 右移后 A-1, Q1, Q-11 第 4 轮: Q01, Q-11 - 保持 右移后 A-1, Q0, Q-11 计算结果: 3 * -2 -6看到最后结果是对的但中间A出现-3和-2在设计上一点不奇怪因为A寄存器内部会临时出现部分积的中间状态这并不是最终结果。有趣的是第2轮“减M”后A-3右移后变成-2这正是之前提到的“算术右移”在起作用符号位参与移动把-3变成了-2等价于除以2并向下取整。4.3 验证用例3负数乘负数再试试-3 × -2。请输入被乘数 M-8~7: -3 请输入乘数 Q-8~7: -2 计算结果: -3 * -2 6这个例子在手工手算时特别容易出错因为你会遇到“Q01, Q-10”需要“减M”而M本身是负数负负得正A的值反而会增加。但代码里的st.A st.A - st.M在C语言里对补码负数运算天然生效不需要你人工转换这就是补码的妙处。5. 我把这份代码用在课程设计里踩过的坑5.1 坑一左移还是右移方向别搞反网上的Booth算法代码有些是“左移”写法那通常是针对无符号或者说面向教学优化过的变形。教材上经典状态机一定是“算术右移”。我在写第一版代码时不小心把 1写成了 1结果3 * 2输出都是乱的。如果你看到中间状态出现数字暴涨优先检查这里。5.2 坑二算术右移和逻辑右移在C语言里的区别C语言标准说对int类型做右移到底是算术右移还是逻辑右移C99标准把无符号数的右移规定为逻辑右移但有符号数是实现定义。GCC在Linux上对负数执行的是算术右移这和硬件里的行为一致。但假如你在某个嵌入式编译器上做实验碰上逻辑右移符号位就会被0填充结果全错。保险的做法是手动写成combined (combined 1) | (combined 0x80 ? 0x80 : 0);这样任何编译器下行为都一致。5.3 坑三迭代次数固定是4轮不是“直到Q变成0”很多初学Booth算法的人会把迭代次数做成while (Q ! 0)这是经典错误。4位补码乘法必须固定迭代4次因为位数决定了符号扩展和中间部分积的收敛过程。如果乘数恰好是0循环会提前退出但如果是负数Q的二进制表示里永远有1或者在右移过程中进入全1状态循环就永远退不出来。我的代码里用了for (iteration 0; iteration 4; iteration)就是要强制走完所有位。5.4 坑四验证时把“仿真输出”和“硬件仿真”混为一谈写C代码只是第一步。课程设计要求往往是Verilog/VHDL实现C代码只是给你当参考“行为模型”。如果你把这份C代码翻译成Verilog最容易被坑的是Verilog的在有符号数和无符号数变量上行为完全不同。我在实际写Verilog时踩了一个大坑reg默认是无符号的如果我先声明一个reg [4:0] A;然后做A A 1;结果符号扩展完全看A的最高位是不是1但问题是A本身存的是一个补码负数符号位扩展没问题问题出在拼接时如果弄错有符号性$signed()转换的位置不同结果就错了。所以C代码里清晰的A、Q、Q-1状态分离反而帮我理清了Verilog的数据通路划分。6. 源码的扩展思路从4位到8位、16位甚至可参数化6.1 如何改成N位补码乘法把代码从4位扩展成N位核心只需要改三处输入范围检查从-8~7改成-(2^(N-1))到2^(N-1)-1。拼接combined时A的位数要比N多1也就是N1位。迭代次数从4改成N。如果追求通用性可以把N做成宏定义#define N 4 #define A_WIDTH (N 1) #define COMBINED_WIDTH (2 * N 1)arithmetic_shift_right里拼接和拆回的逻辑都要用N来算掩码。我当时顺手写了一个版本gcc -D N8就能直接编译成8位版本。这个扩展思路在Verilog里更实用因为Verilog的parameter可以直接控制位数和C的宏定义异曲同工。6.2 从行为模型到可综合Verilog的映射关系如果你跟我一样是“计算机组成原理”课程设计大概率最后要交一份Verilog代码。这里给一个对应关系参考C语言代码Verilog表达关键注意点st.Areg [N:0] A;位宽是N1用于符号扩展st.Qreg [N-1:0] Q;乘数寄存器st.Q_prevreg Q_prev;附加位st.Mreg [N:0] M;被乘数也要扩展一位方便加减时对齐combined 1{A, Q} {A[N], A, Q[N-1]};手工实现算术右移拼接第几轮迭代always (posedge clk) if (count N) ...用计数器控制4轮这张表是我从C代码翻译到Verilog时自己总结的比直接照着教材硬件图一行行敲要快得多。尤其{A, Q} {A[N], A, Q[N-1]}这句本质就是C代码里combined拆开后的硬件写法。6.3 再扩展一步无符号乘法器与补码乘法器共用一套数据通路很多同学做完Booth会好奇那unsigned乘法怎么办实际上Booth算法稍作变形就能同时处理无符号数和有符号数——只需要在最高位迭代时做一次特殊处理。教材里管这个叫“Booth-2”或“扩展Booth”。我没在这篇博文里贴完整代码但思路是无符号数在A最高位补0迭代N次后额外右移一位有符号数就用Booth。两类操作共用同一个移位器和加法器唯一的区别是把符号扩展换成0扩展以及多一次移位。这个点在课程设计答辩时非常加分你可以自己试着扩展一下。7. 我对Booth算法C源码这件事的最终体会代码最终跑通那一刻我才真正理解了为什么教材非要选Booth算法讲乘法器它把“符号”和“数值”彻底融合在补码里所有加减法、移位、判断都是统一的不需要在数据通路上为负号单独开一条路。这份C源码我后来用在了很多地方不仅是在“计算机组成原理”作业里在写一些定点数运算库的时候也借鉴了这种“状态机逐位迭代”的思路。如果你也在准备北航或者其他学校的“计算机组成原理”课程设计我的建议是不要直接复制我这份代码交差先拿纸笔手算两三个用例再对照代码看打印状态最后自己尝试改一改迭代次数或位宽。这样一整套下来比你背十遍Booth算法推导都管用。等你真到了Verilog那一步会发现自己对数据通路的理解已经超过一多半同学了。本文还有配套的精品资源点击获取