CODEWITHSUNDEEP
assemblybinarymultiplicationlc3
gator
gator

Reputation: 3523

Shift multiplication in LC3 Assembly

I can multiply two numbers in binary by doing bitshifting and addition:

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

For the steps of the above, result is changed in this order:

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

I'm having a hard time designing an LC3 assembly algorithm to do the pseudocode above.

    .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

Here's my best attempt. I'm not sure what to do to be honest, LC3 instruction set is very limited. I have a decent grasp on how to multiply using an iterator in LC3 but not using bitwise shifting like this.

Upvotes: 0

Views: 3735

Answers (1)

Jester
Jester

Reputation: 58782

On architectures where you have a shift right instruction, you keep testing the least significant bit by masking it off using and with 1 and shift each bit into this position in a loop. However LC3 does not have shift right, and no easy way to do it either, so it's more convenient to move the mask bit left rather than the multiplier right. To detect end of loop, you can use a fixed count (16 bits) or see if there is any set bit among the remaining bits using another mask. A possible solution could look like:

    .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

Upvotes: 2

Related Questions