Posted on by Kalkicode
Code Bit Logic

# Multiplication of two numbers with shift operator

In this article, we will explore the concept of multiplication of two numbers using the shift operator in the C programming language. The shift operator allows us to perform bitwise operations on binary representations of numbers, making it a useful tool for efficient multiplication.

## Problem Statement

The problem is to implement a function that takes two integer inputs, 'x' and 'y,' and calculates their product using bitwise operations and the shift operator. The function should be able to handle positive and negative numbers as well.

Example: Let's take an example to understand the multiplication process using the shift operator. Consider two positive numbers, 5 and 3.

1. Binary representation of 5: 101
2. Binary representation of 3: 011

Now, we will use the shift operator to perform multiplication:

1st iteration (n=0, b=3): Since the last bit of 3 is 1, we add (5 << 0) to the result, which is 5.

2nd iteration (n=1, b=1): Since the last bit of 1 is 1, we add (5 << 1) to the result, which is 10.

At this point, b becomes 0, and the loop ends. So, the final result is 10, which is the product of 5 and 3.

## Pseudocode

``````function multiply(x, y):
a = x
b = y
status = 0
n = 0
result = 0

if a < 0 and b < 0:
a = -a
b = -b
else if a < 0:
a = -a
status = 1
else if b < 0:
b = -b
status = 1

while b > 0:
if (b & 1) == 1:
result = result + (a << n)
n++
b = b >> 1

if status == 1:
result = -result

return result
``````

## Algorithm Explanation:

1. Start by initializing the variables 'a' and 'b' with the input values 'x' and 'y,' respectively. Also, set 'status,' 'n,' and 'result' to 0.
2. Check if both 'a' and 'b' are negative. If so, make them positive since the product of two negative numbers is always positive.
3. Check if 'a' is negative. If true, make it positive and set 'status' to 1.
4. Check if 'b' is negative. If true, make it positive and set 'status' to 1.
5. Initialize a loop that runs until 'b' becomes 0.
6. Inside the loop, check if the last bit of 'b' is 1 (using bitwise AND operation with 1). If true, add (a << n) to 'result.'
7. Increment 'n' to move to the next bit position.
8. Right-shift 'b' by 1 to remove the last bit from 'b.'
9. After the loop ends, check if 'status' is 1. If true, the result is negative, so make 'result' negative.
10. Return the 'result.'

## Code Solution

Here given code implementation process.

``````// C Program
// Multiplication of two numbers with shift operator
#include <stdio.h>

// Multiply two numbers
void multiply(int x, int y)
{
int a = x;
int b = y;

// Useful counter variables
int status = 0;
int n = 0;

// Use to store result
int result = 0;

if(a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if(a < 0 )
{
// When a is negative
a = -a;

status = 1;
}
else if(b < 0)
{
// When b is negative
b = - b;
status = 1;
}
// Perform multiplication
while(b > 0)
{
if(b & 1 == 1)
{
result = result + (a << n);
}
// increase bit position
n++;
b = b>>1;
}

if(status == 1)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
printf(" ((%d) X (%d)) : %d \n",x,y,result);

}
int main()
{
// Test case
multiply(2,5);
multiply(3,-4);
multiply(-2,-3);
return 0;
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````/*
Java Program
Multiplication of two numbers with shift operator
*/
public class Multiplication
{
// Multiply two numbers
public void multiply(int x, int y)
{
int a = x;
int b = y;
// Useful counter variables
int n = 0;
boolean status = false;
// Use to store result
int result = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b & 1) == 1)
{
result = result + (a << n);
}
// increase bit position
n++;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
System.out.print(" ((" + x + ") X (" + y + ")) : " + result + " \n");
}
public static void main(String[] args)
{
// Test case
}
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Multiplication of two numbers with shift operator
*/

class Multiplication
{
public:
// Multiply two numbers
void multiply(int x, int y)
{
int a = x;
int b = y;
// Useful counter variables
int n = 0;
bool status = false;
// Use to store result
int result = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b &1) == 1)
{
result = result + (a << n);
}
// increase bit position
n++;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
cout << " ((" << x << ") X (" << y << ")) : " << result << " \n";
}
};
int main()
{
// Test case
return 0;
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````// Include namespace system
using System;
/*
C# Program
Multiplication of two numbers with shift operator
*/
public class Multiplication
{
// Multiply two numbers
public void multiply(int x, int y)
{
int a = x;
int b = y;
// Useful counter variables
int n = 0;
Boolean status = false;
// Use to store result
int result = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b & 1) == 1)
{
result = result + (a << n);
}
// increase bit position
n++;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
Console.Write(" ((" + x + ") X (" + y + ")) : " + result + " \n");
}
public static void Main(String[] args)
{
// Test case
}
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````<?php
/*
Php Program
Multiplication of two numbers with shift operator
*/
class Multiplication
{
// Multiply two numbers
public	function multiply(\$x, \$y)
{
\$a = \$x;
\$b = \$y;
// Useful counter variables
\$n = 0;
\$status = false;
// Use to store result
\$result = 0;
if (\$a < 0 && \$b < 0)
{
// Two negative numbers multiplication always positive
\$a = -\$a;
\$b = -\$b;
}
else if (\$a < 0)
{
// When a is negative
\$a = -\$a;
\$status = true;
}
else if (\$b < 0)
{
// When b is negative
\$b = -\$b;
\$status = true;
}
// Perform multiplication
while (\$b > 0)
{
if ((\$b & 1) == 1)
{
\$result = \$result + (\$a << \$n);
}
// increase bit position
\$n++;
\$b = \$b >> 1;
}
if (\$status == true)
{
// When calculated result is negative
\$result = -\$result;
}
// Display calculated result
echo " ((". \$x .") X (". \$y .")) : ". \$result ." \n";
}
}

function main()
{
// Test case
}
main();``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````/*
Node Js Program
Multiplication of two numbers with shift operator
*/
class Multiplication
{
// Multiply two numbers
multiply(x, y)
{
var a = x;
var b = y;
// Useful counter variables
var n = 0;
var status = false;
// Use to store result
var result = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b & 1) == 1)
{
result = result + (a << n);
}
// increase bit position
n++;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
process.stdout.write(" ((" + x + ") X (" + y + ")) : " + result + " \n");
}
}

function main()
{
// Test case
}
main();``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````#   Python 3 Program
#   Multiplication of two numbers with shift operator

class Multiplication :
#  Multiply two numbers
def multiply(self, x, y) :
a = x
b = y
#  Useful counter variables
n = 0
status = False
#  Use to store result
result = 0
if (a < 0 and b < 0) :
#  Two negative numbers multiplication always positive
a = -a
b = -b

elif(a < 0) :
#  When a is negative
a = -a
status = True

elif(b < 0) :
#  When b is negative
b = -b
status = True

#  Perform multiplication
while (b > 0) :
if ((b & 1) == 1) :
result = result + (a << n)

#  increase bit position
n += 1
b = b >> 1

if (status == True) :
#  When calculated result is negative
result = -result

#  Display calculated result
print(" ((", x ,") X (", y ,")) : ", result ," ")

def main() :
#  Test case

if __name__ == "__main__": main()``````

#### Output

`````` (( 2 ) X ( 5 )) :  10
(( 3 ) X ( -4 )) :  -12
(( -2 ) X ( -3 )) :  6``````
``````#   Ruby Program
#   Multiplication of two numbers with shift operator

class Multiplication
#  Multiply two numbers
def multiply(x, y)
a = x
b = y
#  Useful counter variables
n = 0
status = false
#  Use to store result
result = 0
if (a < 0 && b < 0)
#  Two negative numbers multiplication always positive
a = -a
b = -b
elsif(a < 0)
#  When a is negative
a = -a
status = true
elsif(b < 0)
#  When b is negative
b = -b
status = true
end

#  Perform multiplication
while (b > 0)
if ((b & 1) == 1)
result = result + (a << n)
end

#  increase bit position
n += 1
b = b >> 1
end

if (status == true)
#  When calculated result is negative
result = -result
end

#  Display calculated result
print(" ((", x ,") X (", y ,")) : ", result ," \n")
end

end

def main()
#  Test case
end

main()``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6
``````
``````/*
Scala Program
Multiplication of two numbers with shift operator
*/
class Multiplication
{
// Multiply two numbers
def multiply(x: Int, y: Int): Unit = {
var a: Int = x;
var b: Int = y;
// Useful counter variables
var n: Int = 0;
var status: Boolean = false;
// Use to store result
var result: Int = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b & 1) == 1)
{
result = result + (a << n);
}
// increase bit position
n += 1;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
print(" ((" + x + ") X (" + y + ")) : " + result + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Multiplication = new Multiplication();
// Test case
}
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````
``````/*
Swift 4 Program
Multiplication of two numbers with shift operator
*/
class Multiplication
{
// Multiply two numbers
func multiply(_ x: Int, _ y: Int)
{
var a: Int = x;
var b: Int = y;
// Useful counter variables
var n: Int = 0;
var status: Bool = false;
// Use to store result
var result: Int = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b & 1) == 1)
{
result = result + (a << n);
}
// increase bit position
n += 1;
b = b >> 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
print(" ((", x ,") X (", y ,")) : ", result ," ");
}
}
func main()
{
// Test case
}
main();``````

#### Output

`````` (( 2 ) X ( 5 )) :  10
(( 3 ) X ( -4 )) :  -12
(( -2 ) X ( -3 )) :  6``````
``````/*
Kotlin Program
Multiplication of two numbers with shift operator
*/
class Multiplication
{
// Multiply two numbers
fun multiply(x: Int, y: Int): Unit
{
var a: Int = x;
var b: Int = y;
// Useful counter variables
var n: Int = 0;
var status: Boolean = false;
// Use to store result
var result: Int = 0;
if (a < 0 && b < 0)
{
// Two negative numbers multiplication always positive
a = -a;
b = -b;
}
else if (a < 0)
{
// When a is negative
a = -a;
status = true;
}
else if (b < 0)
{
// When b is negative
b = -b;
status = true;
}
// Perform multiplication
while (b > 0)
{
if ((b and 1) == 1)
{
result = result + (a shl n);
}
// increase bit position
n += 1;
b = b shr 1;
}
if (status == true)
{
// When calculated result is negative
result = -result;
}
// Display calculated result
print(" ((" + x + ") X (" + y + ")) : " + result + " \n");
}
}
fun main(args: Array < String > ): Unit
{
// Test case
}``````

#### Output

`````` ((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6``````

## Output Explanation

The code is tested with three cases:

1. multiply(2, 5): The output is ((2) X (5)): 10. The result is correct.
2. multiply(3, -4): The output is ((3) X (-4)): -12. The result is correct.
3. multiply(-2, -3): The output is ((-2) X (-3)): 6. The result is correct.

## Time Complexity

The time complexity of the multiplication algorithm using the shift operator is O(log b), where 'b' is the value of the second input number. This is because the algorithm iterates through the bits of 'b' until 'b' becomes 0, and the number of iterations is determined by the number of bits in 'b.' Therefore, the time complexity is logarithmic with respect to 'b.'

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post