За произволни две числа n и m трябва да намерите n*m, без да използвате оператор за умножение.
Примери:
Input: n = 25 m = 13 Output: 325 Input: n = 50 m = 16 Output: 800
Метод 1
Можем да решим този проблем с оператора за смяна. Идеята се основава на факта, че всяко число може да бъде представено в двоична форма. И умножението с число е еквивалентно на умножение със степени на 2. Степени на 2 могат да бъдат получени с помощта на ляв оператор за смяна.
Проверете за всеки зададен бит в двоичното представяне на m и за всеки зададен бит ляво изместване n пребройте пъти, където пребройте, ако стойността на мястото на зададения бит на m и добавете тази стойност, за да отговорите.
// CPP program to find multiplication // of two number without use of // multiplication operator #include 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 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>
Изход
260
Времева сложност: O(log n)
Помощно пространство: О(1)
Метод 2
Можем да използваме оператор за смяна в цикли.
C++#include 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));
Изход
260
Времева сложност: O(log(m))
Помощно пространство: O(1)
Related Article: Russian Peasant (Multiply two numbers using bitwise operators)Създаване на тест