How to perform multiplication, using bitwise operators?

I was working on a recursive multiplication problem without the * operator and came up with a solution that was informed by the top answer here.

I thought it was worth posting because I really like the explanation in the top answer here, but wanted to expand on it in a way that:

1. Had a function representation.
2. Handled cases where your "remainder" was arbitrary.

This only handles positive integers, but you could wrap it in a check for negatives like some of the other answers.

def rec_mult_bitwise(a,b):
    # Base cases for recursion
    if b == 0:
        return 0
    if b == 1:
        return a

    # Get the most significant bit and the power of two it represents
    msb = 1
    pwr_of_2 = 0
    while True:
        next_msb = msb << 1
        if next_msb > b:
            break
        pwr_of_2 += 1
        msb = next_msb
        if next_msb == b:
            break

    # To understand the return value, remember:
    # 1: Left shifting by the power of two is the same as multiplying by the number itself (ie x*16=x<<4)
    # 2: Once we've done that, we still need to multiply by the remainder, hence b - msb
    return (a << pwr_of_2) + rec_mult_bitwise(a, b - msb)

def multiply(x, y):
     return x << (y >> 1)

You would want to halve the value of y, hence y shift bits to the right once (y >> 1) and shift the bits again x times to the left to get your answer x << (y >> 1).

Using Bitwise operator reduces the time complexity.

In cpp:

#include<iostream>
using name space std;

int main(){
   int a, b, res = 0;           // read the elements
   cin>>a>>b;

   // find the small number to reduce the iterations

   small = (a<b)?a:b;           // small number using terinary operator
   big = (small^a)?a:b;         // big number using bitwise XOR operator

   while(small > 0)             
   {
      if(small & 1)             
      {
         res += big;
      }
      big = big << 1;           // it increases the number << is big * (2 power of big)
      small = small >> 1;       // it decreases the number >> is small / (2 power of small)
   }
   cout<<res;
}

In Python:

a = int(input())
b = int(input())
res = 0    

small = a if(a < b) else b
big  = a if(small ^ a) else b

def multiplication(small, big):
    res = 0
    while small > 0:
        if small & 1:
            res += big
        big = big << 1
        small = small >> 1

        return res

 answer = multiplication(small, big)
 print(answer)