汇编语言中基于移位相加算法实现乘法：如何分解乘数？

嘿，这个问题我之前做汇编实验的时候也折腾过！咱们一步步来搞定这个移位相加乘法器，尤其是在没有左移指令的ISA上，完全可以用你说的自加来实现左移，至于怎么取乘数的每一位，其实也很简单～

你已经摸对了路子：移位相加乘法的本质就是把乘数的每一位拆出来，对应位是1的话，就把当前的被乘数（左移对应位数后）加到结果里。现在咱们要解决两个小问题：

• 怎么取出乘数的每一位（从右到左）
• 用自加实现左移一位的具体操作

最常用的方法是利用右移指令（大部分ISA都会提供逻辑右移）：每次把乘数右移一位，原来的最低位会被移到进位标志位（CF）里，我们只需要判断CF是否为1，就能知道当前处理的位是不是1。

如果你的ISA连右移指令都没有，也可以用除法（除以2）取余数的方式：每次把乘数除以2，余数就是当前的最低位，商作为新的乘数继续处理，直到商为0。

这个你已经想到了！左移一位等价于把数乘以2，所以对被乘数执行一次自加（被乘数 = 被乘数 + 被乘数），就完美实现了无符号数的逻辑左移。比如5（101）自加后变成10（1010），正好是左移一位的结果，完全符合你的需求。

假设我们的ISA支持基础的加载、加法、右移、跳转指令，用三个寄存器来实现：

• R0：存储被乘数（初始值5）
• R1：存储乘数（初始值15）
• R2：存储结果（初始值0）

; 初始化寄存器
LOAD R0, 5       ; R0 = 5（被乘数）
LOAD R1, 15      ; R1 = 15（乘数）
LOAD R2, 0       ; R2 = 0（结果初始化为0）

; 乘法循环开始
MULT_LOOP:
    SHR R1       ; 乘数右移一位，最低位进入进位标志CF
    JC ADD_TO_RESULT  ; 如果CF=1（当前位是1），跳转到相加逻辑
    JMP SHIFT_MULTIPLICAND  ; 否则直接左移被乘数

ADD_TO_RESULT:
    ADD R2, R0    ; 把当前被乘数加到结果里

SHIFT_MULTIPLICAND:
    ADD R0, R0    ; 被乘数自加，实现左移一位
    JNZ MULT_LOOP ; 如果乘数还没变成0，继续循环

; 循环结束，R2就是最终结果75
STORE R2, RESULT_ADDR ; 将结果存入内存地址

咱们手动模拟一遍代码流程，验证结果：

1. 初始状态：R0=5，R1=15，R2=0
2. 第一次循环：
   • R1右移后变成7，CF=1（15的最低位是1）
   • 跳转到ADD_TO_RESULT，R2=0+5=5
   • R0自加变成10，R1=7≠0，继续循环
3. 第二次循环：
   • R1右移后变成3，CF=1
   • R2=5+10=15
   • R0自加变成20，R1=3≠0，继续循环
4. 第三次循环：
   • R1右移后变成1，CF=1
   • R2=15+20=35
   • R0自加变成40，R1=1≠0，继续循环
5. 第四次循环：
   • R1右移后变成0，CF=1
   • R2=35+40=75
   • R0自加变成80，R1=0，循环结束
6. 最终R2=75，和你手动计算的二进制1001011完全一致！

如果你的ISA真的极端到连右移和除法都没有，那可以用位判断+减法来模拟：

• 判断最低位：用乘数减1，如果结果是偶数（或者减1后能被2整除），说明最低位是1；或者用AND指令和1做与运算，结果为1则最低位是1。
• 模拟右移：用循环减2的方式，把乘数减到小于2，记录次数就是商（不过这种效率很低，一般ISA不会这么极端）。

内容的提问来源于stack exchange，提问作者theinfiniteride