Here is one way to do an arithmetic multiply on two positive integers only using <<, >>, and +, without using the * or / operators.
The idea is to keep shifting n1 to the left by 1, as n2 is shifted to the right by 1.
Since a LSR (Logical shift right) by 1 essentially divides a number by 2, there will always be numbers that don't divide evenly, so we have to accumulate the remainders and add it to the total at the end (when n2 == 1).
def multi(n1, n2, rem=0): # rem = remainder
if n2 == 0 or n1 == 0:
return 0
elif n2 == 1:
return n1 + rem
else:
more_rem = n1 if (n2 % 2 == 1) else 0
return multi(n1 << 1, n2 >> 1, rem + more_rem)
To improve performance, we can pick our initial parameters more carefully. If we choose to shift down the initial smaller number and shift up the initial bigger number, this will save performance by quite a bit.
def multiply(n1, n2):
small = n1 if n1 < n2 else n2
big = n1 if n1 > n2 else n2
return multi(big, small)