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**:

- Multiplication using Bitwise operations
- Explanation with 2 step by step examples
- Implementation of Multiplication using Bitwise operations
- 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`

- we keep multiplying

**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

- if

- repeat this till
- 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:

- N is the number to be multiplied.
- 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.