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 2^{n}. 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
‘