Divide two integers without using multiplication, division and mod operator in java

Question

I write down a code which find out quotient after dividing two number but without using multiplication,division or mod operator.

My code

public int divide(int dividend, int divisor) {

    int diff=0,count=0;
    int fun_dividend=dividend;
    int fun_divisor=divisor;
    int abs_dividend=abs(dividend);
    int abs_divisor=abs(divisor);

    while(abs_dividend>=abs_divisor){
        diff=abs_dividend-abs_divisor;

        abs_dividend=diff;
        count++;

    }

    if(fun_dividend<0 && fun_divisor<0){
        return count;
    }
    else if(fun_divisor<0||fun_dividend<0) {
        return (-count);
    }

    return count;

}

My code passes the test cases like dividend=-1, divisor=1 or dividend=1 and divisor=-1. But it cannot pass the test case like dividend = --2147483648 and divisor =-1. However I have a if statement when both inputs are negative.

  if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

When my inputs are -2147483648 and -1 it returned zero. I debugged my code and find out that it cannot reach the the inner statements of while loop. It just check the while loop and terminated and execute

 if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

It is very obvious, both inputs are negative, so I was using Math.abs function to make them positive. But when I try to see the values of variables abs_dividend and abs_divisor they show me negative values.

Integer max can take a 9 digit number. So how could I pass this test case? As per this test case dividend is a 10 digit number which is not valid for a integer range.

As per the test case the output that I get should be 2147483647.

How could I solve the bug?

Thank you in advance.

Answer 1

Try using the bit manipulation for this as follows:

public static int divideUsingBits(int dividend, int divisor) {
        // handle special cases
        if (divisor == 0)
            return Integer.MAX_VALUE;
        if (divisor == -1 && dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;

        // get positive values
        long pDividend = Math.abs((long) dividend);
        long pDivisor = Math.abs((long) divisor);

        int result = 0;
        while (pDividend >= pDivisor) {
            // calculate number of left shifts
            int numShift = 0;
            while (pDividend >= (pDivisor << numShift)) {
                numShift++;
            }

            // dividend minus the largest shifted divisor
            result += 1 << (numShift - 1);
            pDividend -= (pDivisor << (numShift - 1));
        }

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            return result;
        } else {
            return -result;
        }
    }