עבור כל שני מספרים נתונים 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(לוג n)
מרחב עזר: O(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)צור חידון