logo

ضرب رقمين مع عامل التحول

لأي رقمين n وm، عليك إيجاد n*m دون استخدام أي عامل ضرب. 
أمثلة :  

Input: n = 25  m = 13 Output: 325 Input: n = 50  m = 16 Output: 800

الطريقة 1
يمكننا حل هذه المشكلة مع عامل التحول. تعتمد الفكرة على حقيقة أنه يمكن تمثيل كل رقم في شكل ثنائي. والضرب في رقم يعادل الضرب في قوى 2. ويمكن الحصول على قوى 2 باستخدام عامل التحول الأيسر.
تحقق من وجود كل مجموعة بت في التمثيل الثنائي لـ m ولكل مجموعة بتات متبقية Shift n عدد مرات حيث يتم حساب القيمة المكانية للبت المحدد لـ m وإضافة تلك القيمة للإجابة.
 

C++
// 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


تعقيد الوقت : يا(سجل ن)



المساحة المساعدة: يا(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))

سلسلة لتحويل int

المساحة المساعدة: O(1)

  Related Article:      Russian Peasant (Multiply two numbers using bitwise operators)   
إنشاء اختبار