Sunday, March 23, 2014

Division without using *, / or % (Divide Two Integers)

Problem
Divide two integers without using multiplication, division and mod operator.

Solution

Method 1 - Subtract the number until it is less then divisor
Let a be dividend and b be divisor
public int divide(int a, int b) {
 if(b==0) 
 {
  print("\nDivide By Zero Error");
  return Integer.MIN;
 }
 int c=0;
 while(a>=b) // We Repeatedly Checking for the Condition a>=b
 {
  a = a - b; // Subtract b from a, and the new result stored in 'a' itself
  c++; // Incrementing the Count
 }
 return c;
}
This method had been discussed here as well.
Method 2 - Using log
public int divide(int dividend, int divisor) {
    if(divisor == 0)
        return 0;
    if(divisor == 1)
        return dividend;
    if(dividend == divisor)
        return 1;
    if(divisor == 2)
        return dividend >> 1;
         
    boolean sign = false;
    if( (dividend > 0 && divisor < 0) ||
        (dividend < 0 && divisor > 0) )
        sign = true;
         
    if(dividend == Integer.MAX_VALUE && divisor == Integer.MIN_VALUE)
        return 0;
     
    dividend = dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(dividend);
    divisor = divisor == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(divisor);
 //result = floor (power(log (div) - log (divisor))) 
    int result = (int) Math.floor(Math.pow(Math.E, Math.log(dividend) - Math.log(divisor)));
    return sign ? -result : result;
}

Method 3 - Using bitwise operator to subtract (Variant of method 1)

The typical way is to shift and subtract. This is basically pretty similar to long division as we learned it in school. The big difference is that in decimal division you need to estimate the next digit of the result. In binary, that's trivial. The next digit is always either 0 or 1. If the (left-shifted) divisor is less than or equal to the current dividend value, you subtract it, and the current bit of the result is a 1. If it's greater, then the current bit of the result is a 0.
public int divide(int dividend, int divisor) { 
    int current = 1;
    int denom = divisor;
    // This step is required to find the biggest current number which can be
    // divided with the number safely.
    while (denom <= dividend) {
        current <<= 1;
        denom <<= 1;
    }
    // Since we may have increased the denomitor more than dividend
    // thus we need to go back one shift, and same would apply for current.
    denom >>= 1;
    current >>= 1;
    int answer = 0;
    // Now deal with the smaller number.
    while (current != 0) {
        if (dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current >>= 1;
        denom >>= 1;
    }
    return answer;
}


References - stackoverflow,

Reactions:

0 comments:

Post a Comment