Multiplication of two numbers with shift operator
For any given two numbers n and m, you have to find n*m without using any multiplication operator.
Examples :
Input: n = 25 , m = 13 Output: 325 Input: n = 50 , m = 16 Output: 800
Method 1
We can solve this problem with the shift operator. The idea is based on the fact that every number can be represented in binary form. And multiplication with a number is equivalent to multiplication with powers of 2. Powers of 2 can be obtained using left shift operator.
Check for every set bit in the binary representation of m and for every set bit left shift n, count times where count if place value of the set bit of m and add that value to answer.
C++
// CPP program to find multiplication // of two number without use of // multiplication operator #include<bits/stdc++.h> using namespace std; // Function for multiplication int multiply( int n, int m) { int ans = 0, count = 0; while (m) { // check for set bit and left // shift n, count times if (m % 2 == 1) ans += n << count; // increment of place value (count) count++; m /= 2; } return ans; } // Driver code int main() { int n = 20 , m = 13; cout << multiply(n, m); return 0; } |
Java
// Java program to find multiplication // of two number without use of // multiplication operator class GFG { // Function for multiplication static int multiply( int n, int m) { int ans = 0 , count = 0 ; while (m > 0 ) { // check for set bit and left // shift n, count times if (m % 2 == 1 ) ans += n << count; // increment of place // value (count) count++; m /= 2 ; } return ans; } // Driver code public static void main (String[] args) { int n = 20 , m = 13 ; System.out.print( multiply(n, m) ); } } // This code is contributed by Anant Agarwal. |
Python3
# python 3 program to find multiplication # of two number without use of # multiplication operator # Function for multiplication def multiply(n, m): ans = 0 count = 0 while (m): # check for set bit and left # shift n, count times if (m % 2 = = 1 ): ans + = n << count # increment of place value (count) count + = 1 m = int (m / 2 ) return ans # Driver code if __name__ = = '__main__' : n = 20 m = 13 print (multiply(n, m)) # This code is contributed by # Ssanjit_Prasad |
C#
// C# program to find multiplication // of two number without use of // multiplication operator using System; class GFG { // Function for multiplication static int multiply( int n, int m) { int ans = 0, count = 0; while (m > 0) { // check for set bit and left // shift n, count times if (m % 2 == 1) ans += n << count; // increment of place // value (count) count++; m /= 2; } return ans; } // Driver Code public static void Main () { int n = 20, m = 13; Console.WriteLine( multiply(n, m) ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find multiplication // of two number without use of // multiplication operator // Function for multiplication function multiply( $n , $m ) { $ans = 0; $count = 0; while ( $m ) { // check for set bit and left // shift n, count times if ( $m % 2 == 1) $ans += $n << $count ; // increment of place value (count) $count ++; $m /= 2; } return $ans ; } // Driver code $n = 20 ; $m = 13; echo multiply( $n , $m ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find multiplication // of two number without use of // multiplication operator // Function for multiplication function multiply(n, m) { let ans = 0, count = 0; while (m) { // check for set bit and left // shift n, count times if (m % 2 == 1) ans += n << count; // increment of place value (count) count++; m = Math.floor(m / 2); } return ans; } // Driver code let n = 20 , m = 13; document.write(multiply(n, m)); // This code is contributed by Surbhi Tyagi. </script> |
Output
260
Time Complexity : O(log n)
Auxiliary Space: O(1)
Method 2
We can use shift operator in loops.
C++
#include <iostream> using namespace std; int multiply( int n, int m){ bool isNegative = false ; if (n < 0 && m < 0) { n = -n, m = -m; } if (n < 0) { n = -n, isNegative = true ; } if (m < 0) { m = -m, isNegative = true ; } int result = 0; while (m){ if (m & 1) { result += n; } // multiply a by 2 n = n << 1; // divide b by 2 m = m >> 1; } return (isNegative) ? -result : result; } int main() { int n = 20 , m = 13; cout << multiply(n, m); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { public static int multiply( int n, int m){ boolean isNegative = false ; if (n < 0 && m < 0 ) { n = -n; m = -m; } if (n < 0 ) { n = -n; isNegative = true ; } if (m < 0 ) { m = -m; isNegative = true ; } int result = 0 ; while (m> 0 ){ if ((m & 1 )!= 0 ) { result += n; } // multiply a by 2 n = n << 1 ; // divide b by 2 m = m >> 1 ; } return (isNegative) ? -result : result; } public static void main (String[] args) { int n = 20 , m = 13 ; System.out.println(multiply(n, m)); } } // This code is contributed by Pushpesh Raj. |
Python3
def multiply(n, m): is_negative = False if n < 0 and m < 0 : n, m = - n, - m if n < 0 : n, is_negative = - n, True if m < 0 : m, is_negative = - m, True result = 0 while m: if m & 1 : result + = n # multiply a by 2 n = n << 1 # divide b by 2 m = m >> 1 return - result if is_negative else result n = 20 m = 13 print (multiply(n, m)) |
C#
// C# program for the above approach using System; class GFG { public static int multiply( int n, int m){ bool isNegative = false ; if (n < 0 && m < 0) { n = -n; m = -m; } if (n < 0) { n = -n; isNegative = true ; } if (m < 0) { m = -m; isNegative = true ; } int result = 0; while (m>0){ if ((m & 1)!=0) { result += n; } // multiply a by 2 n = n << 1; // divide b by 2 m = m >> 1; } return (isNegative) ? -result : result; } public static void Main () { int n = 20 , m = 13; Console.WriteLine(multiply(n, m)); } } // This code is contributed by Utkarsh |
Javascript
function multiply(n, m) { let isNegative = false ; if (n < 0 && m < 0) { n = -n, m = -m; } if (n < 0) { n = -n, isNegative = true ; } if (m < 0) { m = -m, isNegative = true ; } let result = 0; while (m) { if (m & 1) { result += n; } // multiply a by 2 n = n << 1; // divide b by 2 m = m >> 1; } return (isNegative) ? -result : result; } console.log(multiply(20, 13)); |
Output
260
Time Complexity : O(log(m))
Auxiliary Space: O(1)
Related Article: Russian Peasant (Multiply two numbers using bitwise operators)
Contact Us