Divisez deux entiers sans utiliser les opérateurs de multiplication, de division et de modulo

Dans ce problème, il suffit de diviser deux entiers sans utiliser les opérateurs de multiplication, de division et de modulo. Bien que nous puissions utiliser des opérations d’addition, de multiplication ou de bits.

L'énoncé du problème indique que nous obtiendrons deux entiers x et y. Sans utiliser la multiplication, la division ou l'opérateur modulo, nous devons déterminer le quotient de x divisé par y.

Exemple

Entrée : x=15, y=5

Sortie : 3

Entrée : x=10, y=4

Sortie : 2

Entrée : x=-20, y=3

Sortie : -6

Méthode

Méthode 1 (utiliser des mathématiques simples)

Dans cette méthode, nous utiliserons un algorithme mathématique simple. Vous trouverez ci-dessous des instructions étape par étape sur ce que nous suivrons -

• Nous continuerons à soustraire le diviseur (c'est-à-dire y) du dividende (c'est-à-dire x) jusqu'à ce que x soit supérieur ou égal à y.

• Lorsque y est supérieur à x, c'est-à-dire que le diviseur est supérieur au dividende, le dividende devient le reste et le nombre de soustractions devient le quotient.

• Stockez le nombre de fois que la soustraction est effectuée dans une variable et renvoyez-la, c'est notre résultat souhaité.

Exemple

Ce qui suit est l'implémentation C++ de l'algorithme &minnus;

#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

Copier après la connexion

Complexité temporelle : O(a/b)

Complexité spatiale : O(1)

• Puisque n'importe quel nombre peut être représenté sous la forme de 0 ou de 1, le quotient peut être représenté sous forme binaire à l'aide de l'opérateur de décalage.

• Utilisez une boucle for pour parcourir les positions de bits du diviseur de 31 à 1.

• Trouvez le premier bit où le diviseur, c'est-à-dire b<<
• Lors de la vérification de la position suivante, ajoutez le résultat à la variable temp pour vous assurer que temp+(b<<
• Mettez à jour le quotient à chaque fois en calculant le quotient

  OR 1<<

• Retournez au quotient après avoir mis à jour le symbole correspondant.

#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;
}