We have explained how to compute Multiplication using Bitwise Operations. We can solve this using left shift, right shift and negation bitwise operations.

Table of content:

1. Multiplication using Bitwise operations
2. Explanation with 2 step by step examples
3. Implementation of Multiplication using Bitwise operations
4. Time & Space Complexity

Let us get started with Bitwise Multiplication.

Multiplication using Bitwise operations

Problem

To find multiplication of two numbers num1 and num2 using bitwise operators.

We will solve this using Russian Peasant method of Multiplication.

Basic terms:

• a×b = (a×2)×(b/2)
• if b is even then a×b = (a×2)×(b/2)
• if b is odd then a×b = ((a×2)×(b/2) + a)

Steps to multiply:

• Inside a loop (execute till b>=1)
  • we keep multiplying a with 2 and keep dividing b by 2.
  • if b is odd then, result+=a.
  • multiply a with 2, divide b by 2
  • When b == 1, answer will be result + a

Algorithm

Assume we are given two numbers num1 and num2

• initialize and variable result as 0
  • repeat this till num2 is greater then 0
    • if num2 is odd then add num1 to result
    • halve num2 and double num1 using bitwise shift operators
• print result

Explanation with 2 step by step examples

Example 1: Positive x Positive

Let us take a = 4 and b = 5
as both numbers are positive then a = 4 (0b 0000100) and b = 5 (0b 000101)
initialize result = 0

• 1st iteration: as b is odd then result = 4 (result+=4), a = 8 (0b 000100) and b = 2 (0b 000010)
• 2nd iteration: as b is even then result = 4, a = 16 (0b 001000) and b = 1 (0b 000001)
• 3nd iteration: as b is odd then result = 20 (result+=16), a = 32 (0b 010000) and b = 0 (0b 000000)
• as b==0 (0b 000000) loop will stop and we will get result = 20

Example 2: Positive x Negative

let us take a = 4 and b = -5

if any one of the number is negative then we will set a boolean variable neg=true
and will set both number as positive
then
a = 4 (0b 0000100) and b = 5 (0b 000101)
initialize result = 0

• 1st iteration: as b is odd then result = 4 (result+=4), a = 8 (0b 000100) and b = 2 (0b 000010)
• 2nd iteration: as b is even then result = 4, a = 16 (0b 001000) and b = 1 (0b 000001)
• 3nd iteration: as b is odd then result = 20 (result+=16), a = 32 (0b 010000) and b = 0 (0b 000000)
• as b==0 (0b 000000) loop will stop and and as the neg=true then we will return 2's complement of result = 20
  which is -20 [(~(result)+1)]

Implementation of Multiplication using Bitwise operations

Following is the Implementation of Multiplication using Bitwise operations:

#include<iostream>
using namespace std;

int multiply_bitewise(int a, int b)
{
  int n1 = abs(a), n2 = abs(b), result = 0;
  bool neg = false;
  if(min(a,b)<0 && max(a, b)>=0) neg=true;
  while(n2>0)
  {
    if(n2&1==1) result+=n1;
    n2>>=1; n1<<=1;
  }
  if(neg) return (~(result)+1);
  else return result;
}

int main()
{
  cout<<multiply_bitewise(4, 5)<<endl;
  cout<<multiply_bitewise(4, -5)<<endl;
  cout<<multiply_bitewise(-4, 5)<<endl;
  cout<<multiply_bitewise(-4, -5)<<endl;
  return 0;
}

You can replace the addition operation used in the above code with bitwise addition as well. You can learn about Bitwise Addition here.

Output

20
-20
-20
20

Time & Space Complexity

Time Complexity

The Time Complexity of our Multiplication algorithm is: O(logN * logN)

where:

1. N is the number to be multiplied.
2. logN is the number of bits used to represent N.

This is because as logN bits and for each bits, we do a series of steps which involves one addition which takes a time complexity of O(logN).

As the number of bits is fixed for a datatype on a System (for example 32 bits for Integer), then logN = 32 and hence, multiplication is considered as a constant operation in this aspect.

Using the best algorithm for Multiplication, the Time Complexity will be O(logN loglogN). You can learn more about Multiplication Algorithms here.

Note: This optimized algorithm have been found in 2019 and is widely believed to have reached the theoretical limit but it has not been proved.

Space Complexity

Space Complexity of Bitwise Multiplication is: O(1)
No extra spaces were created during Bitwise Multiplication.

With this article at OpenGenus, you must have the complete idea of Bitwise Multiplication. Enjoy.