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.
- Binary representation of 5: 101
- 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:
- Start by initializing the variables 'a' and 'b' with the input values 'x' and 'y,' respectively. Also, set 'status,' 'n,' and 'result' to 0.
- Check if both 'a' and 'b' are negative. If so, make them positive since the product of two negative numbers is always positive.
- Check if 'a' is negative. If true, make it positive and set 'status' to 1.
- Check if 'b' is negative. If true, make it positive and set 'status' to 1.
- Initialize a loop that runs until 'b' becomes 0.
- 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.'
- Increment 'n' to move to the next bit position.
- Right-shift 'b' by 1 to remove the last bit from 'b.'
- After the loop ends, check if 'status' is 1. If true, the result is negative, so make 'result' negative.
- 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)
{
Multiplication task = new Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
}
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()
{
Multiplication task = Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
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)
{
Multiplication task = new Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
}
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()
{
$task = new Multiplication();
// Test case
$task->multiply(2, 5);
$task->multiply(3, -4);
$task->multiply(-2, -3);
}
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()
{
var task = new Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
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() :
task = Multiplication()
# Test case
task.multiply(2, 5)
task.multiply(3, -4)
task.multiply(-2, -3)
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()
task = Multiplication.new()
# Test case
task.multiply(2, 5)
task.multiply(3, -4)
task.multiply(-2, -3)
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
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
}
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()
{
let task: Multiplication = Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
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
{
var task: Multiplication = Multiplication();
// Test case
task.multiply(2, 5);
task.multiply(3, -4);
task.multiply(-2, -3);
}
Output
((2) X (5)) : 10
((3) X (-4)) : -12
((-2) X (-3)) : 6
Output Explanation
The code is tested with three cases:
- multiply(2, 5): The output is ((2) X (5)): 10. The result is correct.
- multiply(3, -4): The output is ((3) X (-4)): -12. The result is correct.
- 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.'
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.
New Comment