logo

Dviejų skaičių dauginimas naudojant poslinkio operatorių

Bet kokiems dviem skaičiams n ir m turite rasti n*m nenaudodami jokio daugybos operatoriaus. 
Pavyzdžiai:  

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

1 būdas
Šią problemą galime išspręsti su pamainos operatoriumi. Idėja pagrįsta tuo, kad kiekvienas skaičius gali būti pavaizduotas dvejetaine forma. O daugyba iš skaičiaus prilygsta daugybai su 2 laipsniais. 2 laipsnius galima gauti naudojant poslinkio į kairę operatorių.
Patikrinkite kiekvieną nustatytą bitą dvejetainiame m atvaizde ir kiekvieną nustatyto bito poslinkį į kairę n skaičiuokite kartus, kur skaičiuokite, jei m numerio bito vietos reikšmė ir pridėkite tą reikšmę atsakydami.
 

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> 

Išvestis
260


Laiko sudėtingumas: O (prisijungti)



Pagalbinė erdvė: O(1)

2 būdas

Galime naudoti Shift operatorių kilpose.

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)); 

Išvestis
260

Laiko sudėtingumas: O(log(m))

Pagalbinė erdvė: O(1)

  Related Article:      Russian Peasant (Multiply two numbers using bitwise operators)   
Sukurti viktoriną