Multiplication by a power of 2 using Logical shifts in MIPS assembly

43,173

Solution 1

Shifting a number n bits left multiples the number by 2n. For example n << 3 = n*2³ = n*8. The corresponding instruction is

SLL $s1, $s2, 3       # $s1 = $s2 * 8   shift left by 3 bit-positions

To multiply any number you can split the number into sums of power of 2s. For example:

  • n*10 = n*8 + n*2 = (n << 3) + (n << 1)

      SLL $t1, $s2, 1
      SLL $t2, $s2, 3
      ADD $s2, $t1, $t2
    

You can also use a subtraction if it's faster

  • n*15 = n*16 - n = (n << 4) - n

      SLL $t1, $s2, 4
      SUB $s1, $t1, $s2
    

Solution 2

i dont understand how having a number 2^n can help me multiply using an odd multiplicand

Here are some examples for when one of the factors is constant:

// x *= 3
temp = x << 1  // x*2
x = temp + x   // x*2 + x

// x *= 10
temp = x << 1  // x*2
x = temp << 2  // x*8
x = temp + x   // x*2 + x*8

// x *= 15
temp = x << 4  // x*16
x = temp - x   // x*16 - x

EDIT: Since you've now explained that both the multipler and multiplicand are variable (which I don't feel was clear in your original question), I'm updating my answer with an explanation of how to go about doing the multiplication:

The algorithm works like this:

result = 0
shift = 0
foreach (bit in multiplicand) {
    if (bit == 1) {
        result += multiplier << shift
    }
    shift += 1
}

And a MIPS assembly implementation could look like this:

# In: $s1 = multiplier, $s2 = multiplicand
# Out: $t0 = result
move $t0,$zero      # result
mult_loop:
    andi $t2,$s2,1
    beq $t2,$zero,bit_clear
    addu $t0,$t0,$s1  # if (multiplicand & 1) result += multiplier << shift
bit_clear:
    sll $s1,$s1,1     # multiplier <<= 1
    srl $s2,$s2,1     # multiplicand >>= 1
    bne $s2,$zero,mult_loop

Note that I use a loop to make things simpler. But you could unroll the loop if you wanted to (i.e. duplicate the loop body)

Share:
43,173
HappyFeet
Author by

HappyFeet

“Wisdom is not a product of schooling but of the lifelong attempt to acquire it.” ― Albert Einstein

Updated on September 08, 2021

Comments

  • HappyFeet
    HappyFeet about 2 years

    Can someone please give me pointers on how I can go about making a code that multiplies using shifts in MIPS assembly? I don't understand how having a number 2^n can help me multiply using an odd multiplicand


    I currently have this code, I'm trying to make a calculator

    .text
    
    li  $v0, 4 
    la  $a0, ask_1
    syscall
    
    li  $v0,5
    syscall
    move    $s1, $v0
    
    
    li  $v0, 4
    la  $a0, ask_2
    syscall
    
    li  $v0,5
    syscall
    move    $s2, $v0
    
    #sll    $s2, $s2, 3     #$s2 * $s2^3 = result
    srl $s2, $s2, 1
    
    li  $v0, 1
    la  $a0, ($s2)
    syscall
    
    
    .data
    
    ask_1:  .asciiz     "Enter Multiplier\n"
    ask_2:  .asciiz     "Enter Multiplicand\n"
    result: .asciiz         "The Answer is:\n"
    
  • HappyFeet
    HappyFeet about 10 years
    i may not use any looping structure, but am allowed to use sub, add e.t.c
  • HappyFeet
    HappyFeet about 10 years
    Thanks, so how do i get the final answer say n = 3
  • Michael
    Michael about 10 years
    No loops are needed. It can be done with shifts, adds and subs, as I show in my examples.
  • phuclv
    phuclv about 10 years
    n = 3 but n multiplied by how much? Anywayt that's a simple math, you can figure it your own
  • HappyFeet
    HappyFeet about 10 years
    i know how to do this with iterative addition, whilst using one number as a counter, what am asking is: Does n maybe determine how many shifts you perform ?? and is the a way of breaking the number into powers of two automatically in mips,, SORRY, IM JUST REALLY CONFUSED!
  • HappyFeet
    HappyFeet about 10 years
    :( i really dont understand what this " temp = x << 4 // x*16 " means, please dumb it down for me!
  • phuclv
    phuclv about 10 years
    in my example n is a variable multiplicant multiplied by a constant multiplier. The shift is determined by the multiplier. If you mean n is a multiplier then the shift is determined by 1 bits in n, like multiply in binary
  • Michael
    Michael about 10 years
    << is a left shift, i.e. the sll instruction in MIPS assembly. x means the register holding the original value that you want to multiply, and temp means a register (any register) that you use as a temporary.