补码两位乘法的移位补位：由部分积符号位决定补0或补1

最近翻到以前存的笔记文件名就叫《补码两位乘.doc》。说实话当年学计算机组成原理的时候这个知识点让我纠结了挺久尤其是那句“移位补0还是1”——每次做题都要翻课件确认翻了也还是半懂不懂。后来我自己动手推了几遍才真正搞清楚补0还是补1根本不是一个需要死记的结论而是由“被移位的寄存器本身的符号位”决定的。这篇文章就把这件事一次讲透补码两位乘法为什么要移位移位时为什么有的地方补0、有的地方补1以及考试和实操中最容易踩的坑。无论你是刚学组成原理的本科生还是复习考研专业课的选手或者是工作中突然要补底层知识的工程师这篇文章都能帮你把这个细节彻底钉死在脑子里。1. 先把两位乘法的来龙去脉捋清楚1.1 为什么需要“两位乘法”计算机做乘法核心思路是把乘法转化为多次“加法移位”。最早的乘法器就是一位一位地看乘数看到某一位是1就把被乘数加一次然后移一位。这种方法叫原码一位乘逻辑简单但缺点也很明显如果n位乘数就要做n轮加法速度慢而且处理补码负数时特别麻烦。后来出现了Booth算法也就是补码一位乘。它的巧妙之处在于用“乘数最低位和附加位”的组合来决定是加被乘数、减被乘数还是加0。这样负数也能直接参与运算不需要先把负数转成原码。但一位Booth仍然是每轮处理一位乘数n位乘数就要n轮。两位乘法就是在这个基础上提速把乘数每两位分成一组配合一个附加位一次判断两位乘数的等效操作每轮处理两位总轮数直接减半。代价是判定表变复杂了操作种类从“加X/加0”扩展到“加X、加2X、减X、减2X、加0”。两位乘法处理补码负数的能力靠的是对乘数的“三位联合编码”。这里的第三位就是附加位通常叫C或y_{-1}初始为0。每轮看乘数寄存器最低两位和这个附加位决定要做什么操作然后部分积和乘数一起右移两位。1.2 三位判定表和它的魂两位Booth的三位判定表长这样不同教材符号写法略有差异但核心逻辑一致乘数最低三位结合附加位操作000加0001加X010加X011加2X100减2X101减X110减X111加0很多人背这张表背得头疼其实它是有规律的。你可以把乘数看成一段连续的“1区域”进入区域时加X离开区域时减X。三位组合本质上是在判断“这段区域跨了几位”如果连续两个1就一次加2X如果马上要结束就减X或减2X。这里的X指被乘数2X就是被乘数左移一位-X就是被乘数补码的相反数-2X同理。因为操作里出现了±2X部分积就必须预留足够位宽所以工程上普遍给部分积和被乘数使用双符号位甚至三符号位。这也是后面移位补位问题的一个关键伏笔。1.3 移位是算法的“血液循环”很多人把重心放在判定表上觉得移位只是机械动作。实际上移位的正确性才是整个算法的生命线。加法和判定只决定“这一轮部分积变成了什么数”而移位决定“这个数被缩小后还保持不保持补码语义”。换句话说如果移位补位补错了后面的每一轮加法都在错误的状态上累积。更麻烦的是这种错误往往不是立刻爆炸而是到最终结果才显现出“正负号不对”或者“数值差了整整两倍”。这种错误在考试里特别坑人因为你不是没算而是每一步都看起来“好像没错”。所以搞清楚移位时谁补0、谁补1、谁根本不需要补位才是真正掌握两位乘法的分水岭。2. 移位补0还是补1先分清移位对象2.1 部分积不是普通数它必须做算术右移两位乘法每一步做完加法后要把“部分积和乘数”联合右移两位。这里的核心是部分积右移必须采用算术右移也就是高位补符号位。为什么因为部分积在后续步骤中还要继续参与加法。一个补码数如果在右移时高位补0而它本身是负数符号位为1那它的数值含义就会彻底改变。举个例子补码数11.1011表示的是负数如果你右移两位时高位补0变成00.1110这直接从一个负数变成了正数后面的计算全完蛋。算术右移的原则很简单最高位是什么右移后高位移进来的就是什么。正数最高位是0补0负数最高位是1补1。这在双符号位下看更明确只要看最左边的那个符号位。如果部分积存的是11.1011最高符号位是1那右移高位就补两个1如果部分积是00.0101最高符号位是0右移高位就补两个0。从原理上讲补码负数在存储时本来就可以无限扩展符号位高位补1只是把这种扩展显式写出来并不改变数值大小。这就好比你说“欠100块”前面加多少个“欠”字欠的钱数都不变。2.2 乘数寄存器不是补位是搬位初学者最容易犯的错是把乘数寄存器也套用“算术右移补符号位”的规则。实际上乘数寄存器在两位乘法里的角色不是保存一个“带符号数”而是作为一个正在被扫描的窗口。它右移两位时最高两位填入的并不是什么符号扩展而是部分积最低两位搬过来的数据。具体来说整个联合寄存器可以看成一长串部分积A跑在前面乘数寄存器M跟在后面最后还有一个附加位C垫底。右移两位时这串数据的后两位被挤出去最前面的空位用部分积的符号位补充。于是部分积的低两位自然落到了乘数寄存器的高两位里乘数寄存器原来的前三位往低位挪了两格原来最低位被挤出去原来次低位则变成新的附加位C。这就是我反复强调的部分积的补位是“算术补位”补的是符号乘数寄存器的变化是“搬位”是在搬运数据不是在做算术右移。如果你用乘数寄存器的符号位来补高位会把A移过来的低位数据冲掉最终结果的低几位必然错乱。2.3 一句话口诀和两个干净例子口诀其实就一句话部分积看自己的符号位正补0、负补1乘数寄存器只在搬位别给它套算术右移。我拿两个中间状态演示一遍。第一种情况部分积是负数。假设当前部分积A11.1011双符号位为11负数乘数M10011附加位C0。整体右移两位后A变成11.1110。注意看A的高位补了两个1因为它的符号位是1。第二种情况部分积是正数。假设当前部分积A00.0101符号位为0乘数M01101附加位C0。整体右移两位后A变成00.0001高位补的是两个0。两个例子放在一起答案就非常直白了补0还是补1取决于当前部分积的最高符号位而不是被乘数是不是负数也不是乘数是不是负数。3. 实操演示看一次完整的补位过程3.1 准备好用到的补码中间状态为了把移位过程讲清楚我直接截取两位乘法计算过程中的一个中间状态来做演示。这里的任务不是从头算一道题而是让你看清“某一步算完接下来怎么移位补位”。假设计算到某一步时部分积A11.1011乘数寄存器M10011附加位C0。这个状态可能来自某道题里“减X”操作后的结果部分积和负的补码相加得到一个负数。双符号位是11说明它在允许范围内没有溢出。现在要做的是把A、M、C这三部分拼接成一个完整的寄存器串然后整体右移两位。这是每一轮加法之后都要做的固定操作。3.2 负数部分积右移补1先把当前状态写出来A 111011 即 11.1011符号位为1 M 10011 C 0拼接成完整串就是 111011 10011 0。整体右移两位时最前面补的是A的符号位也就是1。补两个1之后再把原来的数据整体往右挪两位右移前111011 10011 0 右移后111110 11100 1拆开看新A 111110 即 11.1110高位补的是1 新M 11100 新C 1这部分就是很多人最疑惑的“补1”场景。为什么要补1因为A的最高位是1A本身是负数只有高位补1这个负数在除以4之后才能保持它仍然是负数而且数值关系正确。3.3 正数部分积右移补0再看一个正数状态。假设某一步之后部分积A00.0101乘数M01101附加位C0。A 000101 即 00.0101符号位为0 M 01101 C 0拼接成 000101 01101 0。右移两位时前面补的是A的符号位0右移前000101 01101 0 右移后000001 01011 0拆开看新A 000001 即 00.0001高位补的是0 新M 01011 新C 0注意新M的高两位是“01”而A移出去的低两位正好是“01”。这就是乘数寄存器高两位接收部分积低位数据的过程。这里没有任何“补符号位”的逻辑纯粹是数据搬家。3.4 每一步都套同一套规则很多同学看教材时会把两个不同步骤弄混。其实你只要记住每轮做完加法后做一次同样的联合右移规则完全一致。A永远按算术右移处理补它自己的符号位M永远接收A的低两位同时把自身数据往下搬C永远更新为搬移前的M次低位。唯一需要留意的是整个算法结束时怎么拼结果。一般来说最终部分积寄存器保存乘积的高位部分乘数寄存器保存乘积的低位部分。具体拼接多少位取决于你给寄存器的位宽设置以及乘数本身有多少位。不同教材的处理细节略有差异考试时以课程讲义为准。但这不影响移位规则本身因为每一轮的补位逻辑是完全统一的。4. 常见错误与排查技巧实录4.1 错误1把乘数的符号当成补位依据我当年就犯过这个错。看到乘数是负数补码最高位是1就下意识觉得右移时应该补1。这个印象来自原码一位乘法或者某些“负数原码右移补1”的记忆残留放到补码两位乘法里就错了。补位依据只看当前部分积A的符号位。乘数是正是负只影响判定表里该加X还是减X不影响A右移时补0还是补1。如果你在题目中发现某一步补位行为和乘数符号“应该”出现的规律对不上不用慌说明你把两个角色的职责搞混了。4.2 错误2部分积用逻辑右移高位一律补0这是最致命的一个错误。部分积是补码数右移必须算术右移。一旦你对负数部分积做逻辑右移高位补0负数直接变成正数后面所有步骤全部白算。这种错误非常隐蔽因为前一步加法的结果可能是正数暂时看不出来等后面某一步部分积变成负数再右移时才会翻车。排查方法是看最终结果的正负号是否和理论一致。如果计算结果是一个正数但实际乘积应该是负数优先检查所有右移操作是不是都用了算术右移。4.3 错误3附加位永远置0有些同学把附加位C当成一个固定为0的辅助位每轮移位后都忘记更新。实际上C初始为0但每一轮右移之后它要被更新为“旧乘数寄存器的次低位”。这个更新非常关键因为下一轮的判定表要用到C。C一旦错三位组合就错加什么数、减什么数全部跟着错。判断C有没有更新的最简单方法就是看乘数M的末位。如果一轮右移后M的低位移到C里了说明更新到位如果C始终是0说明漏了这一步。4.4 错误4符号位位数不够两位乘法里会出现加2X、减2X这意味着部分积的数值范围可能临时超过一位符号位能表达的区间。所以工程实现中部分积和被乘数几乎都用双符号位甚至有的教材用三符号位。如果你只留一个符号位某一步加2X时直接溢出后面的补位和加法全在错误数据上进行。建议做题时统一写双符号位。比如X补写成00.0101-2X补写成11.0110。这样右移时看最高符号位依然是第一位数不会乱。而且双符号位还能帮你及时发现溢出如果两个符号位变成01或10说明结果已经超出可表示范围需要停下来检查。4.5 问题排查速查表现象大概率原因调整方法最终结果正负反了负数部分积右移补了0检查所有A右移是否按符号位补位结果数值整体成倍偏差乘数寄存器被错误地用符号扩展M应按搬位规则不补A的符号位判定表组合总是对不上附加位没有每轮更新右移后让C取旧M次低位加2X或减2X时结果溢出符号位位数不够部分积和被乘数统一用双符号位低位结果混乱乘数寄存器的高位被错误填充M高两位应接收A的低两位这张表是我做了大量例题之后整理出来的基本覆盖了初学者最常见的五类问题。遇到结果不对先别怀疑判定表按表里顺序检查三个地方A的右移方式、M的搬位方式、C的更新方式。5. 写个小脚本验证移位规则5.1 算术右移的Python实现如果你还是觉得抽象建议直接写几行代码验证。我自己的习惯是用Python写一个简单的算术右移函数输入一个补码位串输出右移后的位串。核心逻辑非常简单def arithmetic_right_shift(bits: str, k: int) - str: bits: 补码位串例如 111011 表示双符号位 11.1011 k: 右移位数 返回算术右移后的位串高位补符号位 sign bits[0] return sign * k bits[:-k]配合前面例子跑一下print(arithmetic_right_shift(111011, 2)) # 输出 111110 print(arithmetic_right_shift(000101, 2)) # 输出 000001输出和手工推导完全一致。这个函数虽然短但它把“补0还是补1”的决定权交给了bits的最高位而不是写死补0或补1正好对应文章的核心结论。5.2 联合移位的实现思路完整两位乘法里联合右移还可以继续封装。核心步骤是先取A的低两位再取M的前三位然后生成新的A、M和C。def joint_right_shift(A: str, M: str, C: str): A: 部分积位串如 111011 M: 乘数位串如 10011 C: 附加位0 或 1 返回 (新A, 新M, 新C) old_A_tail A[-2:] # 部分积低两位 old_M_head M[:3] # 乘数前三位 new_A arithmetic_right_shift(A, 2) new_M old_A_tail old_M_head new_C M[-2] # 旧乘数次低位成为新附加位 return new_A, new_M, new_C用文章里的两个中间状态测一下print(joint_right_shift(111011, 10011, 0)) # (111110, 11100, 1) print(joint_right_shift(000101, 01101, 0)) # (000001, 01011, 0)结果和前面手算的一模一样。你把这个函数接到自己的两位乘法模拟器里就能把每一轮的移位细节都打出来再也不用靠猜。5.3 写脚本前必须清楚的三个约定写这类模拟脚本最怕的是没有约定清楚位宽和轮次导致程序输出和教材对不上。我建议动手前先确认三件事。第一部分积用几位。教材里常用双符号位加n位小数也就是总长n2位。比如4位小数时A就是6位。第二乘数寄存器和附加位怎么排。我用的是M取5位1个符号位4位小数后面挂C。第三轮次怎么停。奇偶位数不同最后一轮可能只移位一次或处理方式不同需要仔细对齐讲义里的约定。这些都不影响移位核心规则但会影响最终拼接结果的可比性。代码最大的意义是帮你建立“反馈感”。手工推几步容易出错代码跑一遍直接看到新A、新M、新C很快就能找出你是哪一步的补位逻辑出了问题。最后说一点个人实操体会我后来给学弟学妹讲这个知识点从来不说“记住负数补1”。我只让他们做一件事移位之前先抬头看部分积的最高位是0还是1再决定补什么。这个习惯看着简单但它把“死记结论”变成了“看状态做事”能根治所有移位补位错误。另一个体会是把算术右移单独拆成一个函数、联合移位再拆成一个函数整个两位乘法的逻辑会清爽很多。补位规则就那么一句话部分积补自己的符号位乘数寄存器搬位附加位更新成旧次低位。这句话我写进笔记里以后再也没在这个考点上丢过分。