Multiplication by a power of 2 using Logical shifts in MIPS assembly
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)
HappyFeet
“Wisdom is not a product of schooling but of the lifelong attempt to acquire it.” ― Albert Einstein
Updated on September 08, 2021Comments
-
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 about 10 yearsi may not use any looping structure, but am allowed to use sub, add e.t.c
-
HappyFeet about 10 yearsThanks, so how do i get the final answer say n = 3
-
Michael about 10 yearsNo loops are needed. It can be done with shifts, adds and subs, as I show in my examples.
-
phuclv about 10 yearsn = 3 but n multiplied by how much? Anywayt that's a simple math, you can figure it your own
-
HappyFeet about 10 yearsi 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 about 10 years:( i really dont understand what this " temp = x << 4 // x*16 " means, please dumb it down for me!
-
phuclv about 10 yearsin 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 about 10 years
<<
is a left shift, i.e. thesll
instruction in MIPS assembly.x
means the register holding the original value that you want to multiply, andtemp
means a register (any register) that you use as a temporary.