Dividieren Sie zwei ganze Zahlen, ohne die Multiplikations-, Divisions- und Modulo-Operatoren zu verwenden

Bei diesem Problem müssen wir nur zwei ganze Zahlen dividieren, ohne Multiplikations-, Divisions- und Modulo-Operatoren zu verwenden. Obwohl wir Additions-, Multiplikations- oder Bitoperationen verwenden können.

Die Problemstellung besagt, dass wir zwei ganze Zahlen x und y erhalten. Ohne Multiplikation, Division oder den Modulo-Operator müssen wir den Quotienten von x dividiert durch y bestimmen.

Beispiel

Eingabe: x=15, y=5

Ausgabe: 3

Eingabe: x=10, y=4

Ausgabe: 2

Eingabe: x=-20, y=3

Ausgabe: -6

Methode

Methode 1 (einfache Mathematik verwenden)

Bei dieser Methode verwenden wir einen einfachen mathematischen Algorithmus. Nachfolgend finden Sie eine Schritt-für-Schritt-Anleitung, was wir befolgen werden –

• Wir subtrahieren so lange den Divisor (d. h. y) vom Dividenden (d. h. x), bis x größer oder gleich y ist.

• Wenn y größer als x ist, das heißt, der Divisor größer als der Dividend ist, wird der Dividend zum Rest und die Anzahl der Subtraktionen wird zum Quotienten.

• Speichern Sie die Häufigkeit, mit der die Subtraktion durchgeführt wird, in einer Variablen und geben Sie sie zurück. Dies ist unsere gewünschte Ausgabe.

Beispiel

Das Folgende ist die C++-Implementierung des obigen Algorithmus −

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long division(long long a,long long b) // where a is dividend and b is divisor
{
   long long sign=1;
   if((a<0) ^( b<0))  // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1; 
   }
   long long m=abs(a);
   long long n=abs(b);
   long long count=0; // for storing the quotient 
   while(m>=n){
      m=m-n;
      count++;
   }
   if(sign==-1) // when sign is negative
   {
      count=-count;
   }
   return count;
} 
int main(){
   long long a=-21474;
   long long b=2;
   long long val=division(a,b);
   cout<<val<<endl;
   return 0;
}

-10737

Nach dem Login kopieren

Zeitliche Komplexität: O(a/b)

Raumkomplexität: O(1)

• Da jede Zahl als 0 oder 1 dargestellt werden kann, kann der Quotient mithilfe des Schiebeoperators in binärer Form dargestellt werden.

• Verwenden Sie eine for-Schleife, um die Bitpositionen des Divisors von 31 bis 1 zu iterieren.

• Suchen Sie das erste Bit, bei dem der Divisor, also b<<
• Wenn Sie die nächste Position überprüfen, fügen Sie das Ergebnis zur temporären Variablen hinzu, um sicherzustellen, dass temp+(b<<
• Aktualisieren Sie den Quotienten jedes Mal, indem Sie den Quotienten

  OR 1<< berechnen

• Kehren Sie zum Quotienten zurück, nachdem Sie das entsprechende Symbol aktualisiert haben.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long division(long long a,long long b) // where a is dividend and b is divisor
{
   long long sign=1;
   if((a<0) ^( b<0))  // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1; 
   }
   long long m=abs(a);
   long long n=abs(b);
   long long count=0; // for storing the quotient 
   long long temp=0;
   for (int j = 31; j >= 0; --j){
   
      if (temp + (n << j) <= m){
         temp += n << j;
         count |= 1L << j;
      }
   }
   if(sign==-1) // when sign is negative
   {
      count=-count;
   }
   return count;
   
} 
int main(){
   long long a=49;
   long long b=5;
   long long val=division(a,b);
   cout<<val<<endl;
   a=-18,b=5;
   cout<<division(a,b);
   
   return 0;
}

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long int divide(long long int a,long long int b){
   long long int sign=1;
   if(a==0||b==0) // when a is zero or b is zero
   {
      return 0;
   }
   if((a>0) ^ (b>0)) // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1;
   }
   if(b==1) // when b is 1 then it will return a example 51/1 = 51
   {
      sign==-1?-a:a;
      return a;
   }
   long long int m=abs(a);
   long long int n=abs(b);
   
   //log function return the logarithmic value of the entered value with base e i.e. natural log of the entered value
   //exp function return the value equal to e^(entered value)
   long long int ans =exp(log(m) - log(n)) + 0.0000000001; 
   
   // if it gives the value in decimal we will add from 0.0000000001 to account for accuracy errors
   if(sign==-1) // when sign is negative return the negative ans
   {
      return -ans;
   }
   return ans;
   
}
int main(){
   long long int ans=divide(47,-9);
   cout<<ans<<endl;
   
   return 0;
}