# Relatively Straightforward Java Solution that beats 78%

• So basically what this does is shifts the divisor by a large initial amount. I used 31 since we are dealing with integers, which are 32 bits. Then, if the shifted divisor <= dividend, we move stop and subtract the dividend by the shifted divisor. The shifted divisor will be of the form divisor * 2^k. We keep track of k, and keep adding our result by (1L << k). We don't need to check larger k's once we decrement it to a certain point, because the dividend keeps getting smaller. We also get rid of overflow errors by using longs. This is essentially the method found in Elements of Programming Interviews.

``````public class Solution {
public int divide(int dividend, int divisor) {
long x = dividend;
long y = divisor;

// Take the absolute values and deal with the sign later.
// This is a potential overflow point, so we need to use longs.
// For example, if we have Integer.MIN_VALUE, taking the
// absolute value of that will overflow.
x = Math.abs(x);
y = Math.abs(y);
int power = 31;

// will likely overflow since we're shifting left by 31.
long yPower = y << power;
long result = 0;

// Stop once the dividend is less than the divisor.
// We clearly cannot fit anymore integer multiples of
// the divisor into the dividend.
while(x >= y) {

// We still haven't found a candidate <= dividend.
while(yPower > x) {
yPower >>= 1;
power--;
}

x -= yPower;

// we multiplied the divisor by 2^power, so this is how
// much we can increment result.
result += (1L << power);
}

// check if they have the same sign.
result = (dividend > 0) ^ (divisor > 0) ? 0 - result : result;

// overflow checks. If overflowed, then return max value.
return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE ? Integer.MAX_VALUE : (int) result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.