说实话补码的乘运算这门课刚学时很多人都会被“符号位到底参不参与运算”“最后移位又移的是什么”这些细节绕晕。刷了无数遍王道视频、啃了唐朔飞的教材最后发现核心其实就一句话补码乘法不用单独处理符号位符号位直接参与运算而实现这个“直接参与”的算法就是Booth一位乘法。这篇文章我不讲虚的直接把这套算法的来龙去脉、手算流程、C语言模拟以及我当年踩过的一堆坑全部端出来。1. 先理清基础补码、双符号位和算术右移1.1 补码的编码逻辑为什么二进制世界爱用补码我们学原码、反码、补码的时候总觉得补码就是个“取反加一”的操作。但补码真正的价值在于它把减法统一成了加法。有了补码计算机里就不需要专门的减法器了。这是硬件设计上极其重要的简化。补码的定义可以用“模”来理解。对定点整数来说n1位补码含符号位它的含义是[x]补 2^(n1) x mod 2^(n1)对定点小数来说[x]补 2 x mod 2这个“模”的概念一到位很多问题就通了。比如为什么负数补码取反加一因为要满足 [x]补 [-x]补 ≡ 0 (mod 2^(n1))。加法器里一旦产生最高位的进位就直接丢弃这也是补码运算“模”性质的体现。补码还有一个很重要的性质就是真值 x 和补码的关系可以写成x -x0 Σ(i1 to n) xi * 2^(-i)其中 x0 是符号位。这个公式在Booth算法的推导中会直接用到先记住它。1.2 双符号位到底是干嘛的很多同学看到补码乘法里被乘数要用“双符号位”也叫变形补码就有点懵符号位一个不够还要两个双符号位的本质是给溢出判断留了空间。正常情况下两个符号位应该相同正数两个0负数两个1。如果运算过程中两个符号位变成了01或10那说明结果溢出了。注意补码乘法的过程中部分积是会溢出的如果没有第二个符号位兜底一次进位就可能把符号位冲掉导致后续计算全错。举个例子两个负数相加符号位都是1正常两个1相加会有进位。如果只有一个符号位这个进位直接覆盖了符号位本身得到的结果符号就反了。双符号位可以多接住一次进位让结果保持正确。补码乘法过程中“先加后移”的操作模式中间结果很容易出现需要双符号位才能正确表示的情况。1.3 算术右移和逻辑右移的区别千万别搞混移位是补码乘法的核心操作但很多同学手算时最爱在这里翻车。右移分两种。逻辑右移就简单粗暴高位一律补0。而对补码来说逻辑右移会改变负数的真值因为补码的负数是高位一连串1你在左边补0这个数的数值意义就变了。算术右移不一样它右移时左边补的是符号位本身。正数高位补0负数高位补1这样每右移一位就相当于真值除以2。补码乘法里的部分积右移必须用算术右移。乘数寄存器Q在联合移位时最高位接收的是ACC的最低位移过来的数据而不是保持自己的符号位这个细节后文再细讲。2. 深入Booth一位乘法从原码乘法的痛点说起2.1 原码乘法的麻烦在哪原码一位乘法大家应该都知道符号位单独异或处理数值位绝对值相乘每步根据乘数当前最低位是1还是0决定加不减被乘数绝对值然后右移一位。最大的问题有两个。第一符号位单独处理那硬件上要么多一个符号判断逻辑要么额外多一次异或。第二乘数的符号位在移位过程中是特殊处理的不能完全当作普通位来移。这在硬件实现上就得多出控制逻辑不够统一。补码乘法如果能做到符号位和数值位“一视同仁”硬件实现就简洁多了。Booth一位乘法就是干这件事的。2.2 Booth算法的核心推导从相邻位的差值出发我当初学Booth算法的时候最不理解的就是为什么每次要盯着乘数的最低两位而且是Q0和附加位Q_(n1)这一对“相邻位”来判决。这里的逻辑推导很漂亮。设乘数 y 的补码是 y0.y1 y2 ... yn根据1.1节那个补码真值公式y -y0 y12^(-1) y22^(-2) ... yn*2^(-n)现在我们来做一个小把戏把这个式子改写一下。引入一个 y_(n1) 0这就是附加位的来历可以把 y 改写成y (y1 - y0)*2^0 (y2 - y1)*2^(-1) (y3 - y2)*2^(-2) ... (0 - yn)*2^(-n)你展开一下就能验证y1的系数是 1 - 1/2 1/2y2的系数是 1/2 - 1/4 1/4以此类推最后yn的系数还是2^(-n)而 -y0 项完整保留。所以这个展开式和原式完全等价。最关键的是每个括号 (y_(i1) - y_i) 只会是 -1、0、1 三种值。括号等于0就什么都不加括号等于1就加被乘数括号等于-1就减被乘数也就是加被乘数的相反数即加[-x]补。判决依据就看当前相邻两位y_i y_(i1)00 或 11差值0加001差值1加[x]补10差值-1加[-x]补这就是Booth算法那张判决表的来历完完全全从数学上推导出来的不是拍脑袋定的规则。2.3 寄存器布局ACC、MQ、附加位硬件或模拟过程中我们需要三样东西ACC累加器存放部分积采用双符号位加n位数值位的格式。初始为0MQ乘商寄存器存乘数y的补码单符号位加n位数值位。初始就是[y]补附加位C在MQ的最低位后面额外加一位初始值固定为0这里要特别注意位宽。假设数值位有n位那么ACC是n2位双符号位 n位数值MQ是n1位1符号位 n位数值再加1位附加位。手算时经常写成ACC 00.0000这里假设n4双符号位4位数 MQ 1.0101y的补码单符号位4位数 附加位 02.4 算法流程几轮判决几次移位补码一位乘法Booth法的完整流程初始化ACC0MQ[y]补附加位0重复以下过程n1次检查MQ最低位Q0和附加位C的取值组合按组合表对ACC加对应值0、[x]补或[-x]补若还未到第n1次则ACC、MQ、附加位联合右移一位算术右移最后一次第n1次只做判决加法不再右移注意我这里特别写了“n1次判决、n次移位”。这是很多资料里最容易让新手混乱的细节。有的教材写成“n次加法和n次右移”那种写法通常默认最后一次加法已经含在初始状态里。咱们按n1次判决来算思路是干净的。为什么最后一次不右移因为前面的n次右移已经把部分积放到了正确的位置最后一步加完就是最终结果如果再右移就等于整体多除了一个2结果就错了。3. 完整手算x0.1101y-0.10113.1 准备数据确定码制来看一个最经典的考研级例题。设x 0.1101y -0.1011先把所有码制都写清楚[x]补 00.1101双符号位[-x]补 11.0011这是 x 相反数的补码也就是对[x]补整体再取一次相反数[y]补 1.0101单符号位MQ初始值附加位初始 0数值位n4所以整体流程是5次判决、4次右移。这里有个容易出错的地方[-x]补是怎么来的是对 00.1101 连同符号位一起取反加一得到 11.0010 1 11.0011。很多同学手算时只对数值位取反符号位不动那就错了。补码的求相反数操作符号位是连坐的。3.2 五位判决、四次移位的完整过程我直接给一张我当年复习时自己整理的过程表每一行对应一次判决加移位后的状态。步骤判决组合(Q0 C)操作ACCMQ附加位C初始--00.00001.01010110Q01,C0ACC[-x]补右移11.0011 → 右移后 11.10011.10101201Q00,C1ACC[x]补右移11.100100.110100.0110 → 右移后 00.00110.11010310Q01,C0ACC[-x]补右移00.001111.001111.0110 → 右移后 11.10110.01101401Q00,C1ACC[x]补右移11.101100.110100.1000 → 右移后 00.01000.00010510Q01,C0ACC[-x]补不移位00.010011.001111.01110.00010强调一下表里的MQ我写的是移完之后的完整值看起来“符号位”变了但那已经不是乘数符号了它只是ACC最低位移过来之后的数据别再用乘数符号的视角看它。3.3 结果拼接与验证第5步结束后ACC11.0111MQ0.0001。最终结果怎么拼乘积总位数是2n2位即双符号位2位8位数值位。取ACC完整的6位11.0111再接上MQ的低4位因为MQ高1位是移位过程中从ACC挤过来的不是有效数值位。所以乘积 11.0111 0001 11.01110001来验证一下。真值计算0.1101 13/16-0.1011 -11/16乘积 -143/256。看补码 11.01110001这是负数。数值位 01110001取反加一10001110110001111 143。确实是 -143/256。完全吻合。所以整个手算过程验证下来Booth算法每一步都自洽。建议你自己独立算一遍尤其注意第2步和第4步加完之后的ACC进位情况感受一下双符号位是怎么“吞掉”进位的。4. C语言模拟Booth乘法把算法跑起来手算懂了之后我建议你写个几十行的C语言程序把它模拟一遍。写代码的过程能把很多模糊的细节逼出来比如位宽截断、右移方向、附加位更新时机。下面是我当时的一个精简版本核心逻辑都在。#include stdio.h // 用整数的低6位表示ACC双符号位4位数值 // 用整数的低5位表示MQ单符号位4位数值 // 为了清晰这里每一步都打印状态 int main() { // 准备数据x0.1101, y-0.1011 int x 0b001101; // [x]补 00.1101 int neg_x 0b110011; // [-x]补 11.0011 int mq 0b10101; // [y]补 1.0101 int acc 0; // 部分积初始为0 int c 0; // 附加位Q(n1)初始0 int mask_acc 0x3F; // 保留6位 int mask_mq 0x1F; // 保留5位 printf(初始: ACC%06b MQ%05b C%d\n, acc, mq, c); for (int step 1; step 5; step) { // n1 5次判决 int q0 mq 1; int combo (q0 1) | c; // 高1位是Q0低1位是C if (combo 0b01) { acc (acc x) mask_acc; // 01加[x]补 printf(步骤%d: 组合01ACC[x]补 - %06b\n, step, acc); } else if (combo 0b10) { acc (acc neg_x) mask_acc; // 10加[-x]补 printf(步骤%d: 组合10ACC[-x]补 - %06b\n, step, acc); } else { printf(步骤%d: 组合00或11ACC0 - %06b\n, step, acc); } if (step 5) { // 前4次右移最后一次不移 int sign (acc 5) 1; // 取ACC符号位 // 把ACC(6位)、MQ(5位)、C(1位)拼成一个12位数再整体右移 int total (acc 6) | (mq 1) | c; total (total 1) | (sign 11); // 算术右移高位补符号位 total 0xFFF; acc (total 6) mask_acc; mq (total 1) mask_mq; c total 1; printf( 右移后: ACC%06b MQ%05b C%d\n, acc, mq, c); } } printf(最终: ACC%06b MQ%05b C%d\n, acc, mq, c); return 0; }这段代码的思路就是严格按照表里的流程来走。关键点在于“联合右移”那一步把ACC、MQ、附加位三个寄存器拼成一个连续的位串整体右移一位左端补的是ACC的符号位sign而不是补0。这就是算术右移在寄存器级别的实现。运行结果你会看到每一步的状态变化和第三章那个手算表一一对应。我当初调这个代码时就发现如果右移时忘了补符号位最后一位的结果必然对不上这本身就是理解算术右移最好的实验。5. 常见错误与排查技巧实录5.1 附加位初始值的坑附加位初始必须是0。很多人会问为什么乘数补码后面还要人为加一个0回到2.2节的推导我们是引入 y_(n1)0 来做相邻位差的所以这个初始0是推导过程的一部分不是随便加的。但如果乘数是负数补码比如1.0101把它当成一个整体附加位还是0不要因为符号位是1就把附加位也置1。5.2 移位时补0还是补符号位一定要分清部分积ACC右移时必须补符号位也就是算术右移。很多同学在这里用逻辑右移给负数部分积补了个0结果每移一次数值就错一次。最简单的方法就是用我代码里的思路先取ACC最高位然后整体右移时把这一位补到最前面。补码的算术右移等价于真值除以2这是整个算法的数学基础破坏了这一点后续全部错。还有一个易错点MQ在联合右移时最高位接收的是ACC移出来的最低位不是保持MQ自身的符号位。MQ的符号位在第一次移位后就没有意义了它只是乘积低位的临时存放处。手算时不要看到MQ里符号位变了就觉得是错。5.3 最后一次到底要不要移位答案是最后一次判决后不右移。原因前面说过Booth法的迭代公式决定了第n1次加法之后恰好是最终结果。如果你多右移一次结果等于整体除以2符号位也可能被破坏。考试时算到最后一位一定要停下来别顺手又移一次。5.4 结果拼接时MQ的位宽问题这是最隐蔽的一个坑。我曾见过不少同学算完ACC11.0111、MQ00001后直接把两者拼成11.011100001多了一位结果怎么验都不对。正确做法是最终乘积取ACC完整6位 MQ的低4位也就是去掉MQ的最高位。因为MQ总共5位最高位在移位过程中接收的是ACC的最低位移过来的值它实际是乘积的中间扩展位不构成最终乘积的有效数值。拼接后应该是11.01110001而不是11.011100001。多出来的那一位会让结果凭空多一个2的负幂次误差就出来了。5.5 双符号位溢出判断运算过程中如果ACC两个符号位不一致比如变成了01或者10说明这一步加法溢出了。但在Booth算法里这种情况大多不是真正的溢出而只是中间结果超出了单符号位的表示范围双符号位正好兜住了。操作上不用特殊处理继续移位就行符号位会自动调整回来。真正需要警惕的是最终结果的两个符号位不一致那说明乘积本身超出可表示范围这时候才叫真溢出。5.6 考研、期末常考题型速查题型考察点易错点给x、y补码手算Booth乘法判决表记忆、移位次数最后一次移位、MQ位宽判断补码乘法溢出双符号位判决把中间状态误判为溢出补码右移一位求值算术右移规则负数补0的错误求[-x]补符号位一起取反加一只对数值位取反结果真值转换补码转真值忘了符号位影响5.7 我的独家记忆技巧最后分享几个我当年死磕出来的小技巧。第一判决表别死记。你就想“01”是从0变1相当于乘数在这一位上从无到有所以要加被乘数[x]补“10”是从1变0相当于从有到无所以要减被乘数加[-x]补。00和11就是没变化加0。这样记比背表稳得多。第二移位次数记“n次移位n1次判决”。数值位是4位就右移4次、判断5次数值位是8位就右移8次、判断9次。这是通用规律。多出来的一次就是不右移的收尾加法。第三手算时把ACC、MQ、附加位三个东西竖着排每做完一步就更新一整行用箭头标出“右移”前后状态。这样最后出了错也能顺着表往回查比闷头算到底再回头找错快得多。Booth一位乘法只是补码乘法入门后面还有补码两位乘法Booth两位乘、阵列乘法器、流水线乘法器等等但核心的判决思维和移位思想是互通的。把这张表吃透、把例子亲手算三遍、把代码跑通补码乘法这一块就稳了。