×

Search anything:

# Multiplication using bitwise operations

#### Algorithms bitwise algorithm

Get this book -> Problems on Array: For Interviews and Competitive Programming

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.

#### Vikram Shishupalsingh Bais

Vikram Shishupalsingh Bais is an Open source enthusiast, competitive programmer skilled in programming languages C++, Python, Java, C. He has been an Intern at OpenGenus.