Divide two integers without using the multiplication, division, and modulo operators

In this problem, we only need to divide two integers without using multiplication, division and modulo operators. Although we can use addition, multiplication or bit operations.

The problem statement states that we will get two integers x and y. Without using multiplication, division, or the modulo operator, we need to determine the quotient of x divided by y.

Example

Input: x=15, y=5

Output: 3

Input: x=10, y=4

Output: 2

Input: x=-20, y=3

Output:-6

method

Method 1 (Using Simple Math)

In this method, we will use a simple mathematical algorithm. Here are the step-by-step instructions for what we will follow -

• We will continue to subtract the divisor (i.e. y) from the dividend (i.e. x) until x is greater than or equal to y.

• When y is greater than x, that is, the divisor is greater than the dividend, the dividend becomes the remainder, and the number of subtractions becomes the quotient.

• Store the number of times the subtraction is performed in a variable and return it, this is the output we want.

Example

The following is the C implementation of the above algorithm &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;
}

Output

-10737

Time complexity: O(a/b)

Space complexity: O(1)

Method 2 (using bit operations)

• Since any number can be represented in the form of 0 or 1, the quotient can be represented in binary form using the shift operator.

• Use a for loop to iterate the bit positions of the divisor from 31 to 1.

• Find the first bit where the divisor, that is, b

• When verifying the next position, add the result to the temp variable to ensure that temp (b

• Update the quotient each time by calculating the quotientOR 1

• Return to the quotient after updating the corresponding symbol.

Example

The following is the C implementation of the above method -

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

Output

9
-3

Time complexity: O(log(a))

Space complexity: O(1), because it does not use extra space.

Method 3 (using logarithmic function)

In this method, we will use a simple logarithmic function to calculate the quotient.

As we all know,

$$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$

can be further modified to

$$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$

So this is the basic idea to solve the given problem using this efficient method.

Below are step-by-step instructions for the method we will follow -

• If one of them (i.e. dividend or divisor) is 0, we will return 0.

• Now we will check the symbol using the exclusive OR function (XOR) to store the symbol in a variable.

• If the divisor is 1, the dividend is returned directly.

• Now, declare a variable and use the exp function and the log function.

• Log and exp are built-in functions in C. The log function returns the natural logarithm of the input number, and exp returns a value equal to e plus the input value.

Example

The following is the C implementation of the above method -

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

Output

-5

Time complexity: O(1), , because it takes constant time to perform this operation.

Space complexity: O(1), because it does not use extra space.

in conclusion

In this article, we learn to divide two integers without using multiplication, division, or modulo operators. We learned to solve problems in different ways with different efficiencies. They use simple mathematics, bit operations, and logarithmic functions. Among them, using the logarithmic function is the most efficient method because its time complexity is O(1), which is the smallest among all methods.

I hope this article helped you solve all the concepts regarding this topic.

The above is the detailed content of Divide two integers without using the multiplication, division, and modulo operators. For more information, please follow other related articles on the PHP Chinese website!