Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

• Both dividend and divisor will be 32-bit signed integers.

• The divisor will never be 0.

• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

OOOkkk. So that is a lots of restrictions in this question. Good thing is there is no mention of time and space constraints.

So this problem can be solved in 2 ways.

1. Using bitwise operator

2. Using logarithms.

We shall discuss both of the topics in this tutorial.

So first what is division?

It is another way of multiplication. Think about it.

10/5 = 2. It means that 5 can be multiplied 2 times to get 10. Right simple.

Use left shift operator “<<” to do multiplication. If you left shift a number by 1, then it is equal to multiply that number by 2.

Use right shift operator “>>” to do division. If you right shift a number by 1, then it is equal to division that number by 2.

So keeping this in mind, we shall solve the problem.

We have dividend and divisor.

Step 1: Check if Dividend is greater than or equal to Divisor

Step 2: We left shift the divisor and check if the result is less than dividend. If less, left shift a counter. Store the result in temp variable.

Step 3: Again left shift the above result and the counter. Check again if the result is less than dividend. If less, then continue with this step.

Step 4: If the result is greater than dividend, then we right shift both the counter and temp variable and save the new counter value in the final result.

And we decrement the dividend with the new value of temp.

Step 5: Go back to step 1.

We can write the below pseudo code from the steps we discussed:

while(Dividend >= Divisor)
{
long temp = Divisor, count = 1;
	while(temp <= Dividend)
	{
           	 	temp <<= 1;
            		count <<= 1;
    	}
	result = result + (count >> 1);
	Dividend = dividend – (temp >> 1);
}

Let us take an example and analyse it:

Dividend = 33
Divisor = 3

Pass 1 of Outer loop
	33 >= 3 true
		temp = 3
		count = 1

		Pass 1 of inner loop
			3 <= 33 true

			temp = 6
			count = 2

		Pass 2 of inner loop
			6 <= 33 true

			temp = 12
			count = 4

		Pass 3 of inner loop
			12 <= 33 true

			temp = 24
			count = 8

		Pass 4 of inner loop
			24 <= 33 true

			temp = 48
			count = 16

		Pass 5 of inner loop
			48 <= 33 false
			come out of inner loop

	result = 0 + (16>>1) = 0 + 8
	dividend = dividend - (48 >>1) = 33 - 24 = 9

Dividend = 9
Divisor = 3

Pass 2 of Outer loop

temp = 3
count = 1

		Pass 1 of inner loop
			3 <= 9 true

			temp = 6
			count = 2

		Pass 2 of inner loop
			6 <= 9 true

			temp = 12
			count = 4

		Pass 3 of inner loop
			12 <= 9 false

	result = 8 + (4>>1) =8 + 2 = 10
	dividend = dividend - (12 >>1) = 9 - 6 = 3
Dividend = 3
Divisor = 3

Pass 3 of Outer loop
				
temp = 3
count = 1

		Pass 1 of inner loop
			3 <= 3 true

			temp = 6
			count = 2

		Pass 2 of inner loop
			6 <= 3 false

	result = 10 + (2 >>1) =10 + 1 = 11
	dividend = dividend - (6 >>1) = 3 - 3 = 0

Thus we get the quotient = 11

#include<iostream>
using namespace std;

 int myDivision(int dividend, int divisor) 
 {
 	int result = 0;
  
	while(dividend >= divisor)
	{
        int temp = divisor;
        int count = 1;
        while(temp <= dividend)
        {
            temp <<= 1;
            count <<= 1;
        }
        result = result + (count >> 1 );
        dividend = dividend - (temp >> 1);
    }

    // check if the result should be negative
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;

    return (sign * result);
}



int main()
{
	cout <<"The result of division of 33 by 3 is  " <<myDivision(33, 3)<<endl;
}

The result of division of 33 by 3 is 11

2. Using logarithms.

The solution in C++

#include<iostream>
#include<math.h>
using namespace std;

 int myDivision(int dividend, int divisor) 
 {

        long result = double(exp(log(abs(dividend))-log(abs(divisor))));

    // check if the result should be negative
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;

    return (sign * result);
    
}

int main()
{
	cout <<"The result of division of 33 by 3 by logarithm is  " <<myDivision(33, 3)<<endl;
}

Output:

The result of division of 33 by 3 by logarithm is  11