Pre akékoľvek dané dve čísla n a m musíte nájsť n*m bez použitia akéhokoľvek operátora násobenia.
Príklady:
Input: n = 25 m = 13 Output: 325 Input: n = 50 m = 16 Output: 800
Metóda 1
Tento problém vieme vyriešiť s operátorom zmeny. Myšlienka je založená na skutočnosti, že každé číslo môže byť reprezentované v binárnej forme. A násobenie číslom je ekvivalentné násobeniu s mocninou 2. Mocniny 2 možno získať pomocou operátora ľavého posunu.
Skontrolujte pre každý nastavený bit v binárnej reprezentácii m a pre každý nastavený bitový posun doľava n počítajte časy, kde sa počíta ak miesto hodnoty nastaveného bitu m a pridajte túto hodnotu k odpovedi.
// 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>
Výstup
260
Časová zložitosť: O (log n)
Pomocný priestor: O(1)
java generátor náhodných čísel
Metóda 2
Môžeme použiť operátor posunu v slučkách.
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));
Výstup
260
Časová zložitosť: O(log(m))
parciálny derivát latexu
Pomocný priestor: O(1)
Related Article: Russian Peasant (Multiply two numbers using bitwise operators)Vytvoriť kvíz