LC3汇编中的移位乘法

Question

我可以通过位移和加法将两个二进制数相乘:

int multiplicand = 5; //0101
int multiplier = 3; //0011
int result = 0; //0000
for n bits in multiplier
    if n is one
        result += multiplicand
    multiplicand bit shifted left

以上步骤，结果按顺序变化：

0000 + 0101 -> 0101
0101 + 01010 -> 1111
Skip 1111 + 010100
Result is 1111 (15)

我很难设计一个 LC3 汇编算法来执行上面的伪代码。

    .orig x3500     ; starting position
    and r0, r0, #0  ; result
    ld r1, m1       ; load multiplicand
    ld r2, m2       ; load multiplier
l1  brz l2          ; if bit is zero
    brp l3          ; if bit is one
    brn l4          ; if no more bits (???)
l2  add r1, r1, r1  ; shift multiplicand bits left
    brnzp l1        ; redo
l3  add r0, r0, r1  ; add multiplicand to result
    add r1, r1, r1  ; shift multiplicand bits left
    brnzp l1        ; redo
l4  trap x25        ; end
m1  .fill #5        ; multiplicand
m2  .fill #3        ; multiplier
    .end

这是我最好的尝试。老实说，我不确定该怎么做，LC3 指令集非常有限。我非常了解如何在 LC3 中使用迭代器进行乘法运算，但不使用像这样的按位移位。

Answer 1

在具有右移指令的体系结构中，您通过使用 and 和 1 将其屏蔽并在循环中将每个位移至该位置来继续测试最低有效位。然而 LC3 没有右移功能，也没有简单的方法可以做到这一点，因此将掩码位向左移动比将乘数向右移动更方便。要检测循环结束，您可以使用固定计数（16 位）或使用另一个掩码查看剩余位中是否有任何设置位。可能的解决方案如下所示：

    .orig x3500     ; starting position
    and r0, r0, #0  ; result
    ld r1, m1       ; multiplicand
    ld r2, m2       ; multiplier
    add r3, r0, #1  ; mask for testing bit
    add r4, r0, #-1 ; mask for end condition (all 1 bits)
l1  and r2, r2, r4  ; any bits remaining?
    brz l4          ; no, done
    and r5, r2, r3  ; test bit
    brz l2          ; if bit is zero, skip addition
    add r0, r0, r1  ; add multiplicand to result
l2  add r1, r1, r1  ; shift multiplicand bits left
    add r3, r3, r3  ; shift test mask left
    add r4, r4, r4  ; shift end mask left
    brnzp l1        ; redo
l4  trap x25        ; end
m1  .fill #5
m2  .fill #3
    .end

LC3汇编中的移位乘法

Shift multiplication in LC3 Assembly

binary

assembly

multiplication

lc3