Skip to main content

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)
	{
		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:

  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.'

Last updated on by Kalkicode




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.

New Comment