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  #include  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<
        

         Copy after login
        
       

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 quotientOR1<

• Return to the quotient after updating the corresponding symbol.

Example

The following is the C implementation of the above method -

#include  #include  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<
        

         Copy after login
        
       

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 theexp< 将等于 $\mathrm{e^{(In(a)\:-\:In(b))}}$ 的值存储在其中/b> function and thelogfunction.

• 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.

#include  #include  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<
         

          Copy after login
         
        

-5