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

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

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

n

SLL $s1, $s2, 1n

n

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

n

    n

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

    n

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

    n

  • n

n

You can also use a subtraction if its faster

n

    n

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

    n

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

    n

  • n

b’

n

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

n

n

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

n

// x *= 3ntemp = x << 1  // x*2nx = temp + x   // x*2 + xnn// x *= 10ntemp = x << 1  // x*2nx = temp << 2  // x*8nx = temp + x   // x*2 + x*8nn// x *= 15ntemp = x << 4  // x*16nx = temp - x   // x*16 - xn

n


n

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

n

The algorithm works like this:

n

result = 0nshift = 0nforeach (bit in multiplicand) {n    if (bit == 1) {n        result += multiplier << shiftn    }n    shift += 1n}n

n

And a MIPS assembly implementation could look like this:

n

# In: $s1 = multiplier, $s2 = multiplicandn# Out: $t0 = resultnmove $t0,$zero      # resultnmult_loop:n    andi $t2,$s2,1n    beq $t2,$zero,bit_clearn    addu $t0,$t0,$s1  # if (multiplicand & 1) result += multiplier << shiftnbit_clear:n    sll $s1,$s1,1     # multiplier <<= 1n    srl $s2,$s2,1     # multiplicand >>= 1n    bne $s2,$zero,mult_loopn

n

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)

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

to multiply a number by 2, you just shift it to the left.nTo divide it by to, shift it to the right.

n

Example : 2 = 10 (binary)n-> 2*2 = 4 -> 4 = 100 (binary) = SLL(2) = SLL(10) (binary)

n

The MIPS instruction would be : SLL $s1, $s2, 1

Leave a Reply

Your email address will not be published.