Recursive multiply function in Python using + and binary shifts

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)