public int divide(int dividend, int divisor) {
//Reduce the problem to positive long integer to make it easier.
//Use long to avoid integer overflow cases.
int sign = 1;
if ((dividend > 0 && divisor < 0)  (dividend < 0 && divisor > 0))
sign = 1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
//Take care the edge cases.
if (ldivisor == 0) return Integer.MAX_VALUE;
if ((ldividend == 0)  (ldividend < ldivisor)) return 0;
long lans = ldivide(ldividend, ldivisor);
int ans;
if (lans > Integer.MAX_VALUE){ //Handle overflow.
ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
ans = (int) (sign * lans);
}
return ans;
}
private long ldivide(long ldividend, long ldivisor) {
// Recursion exit condition
if (ldividend < ldivisor) return 0;
// Find the largest multiple so that (divisor * multiple <= dividend),
// whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
// Think this as a binary search.
long sum = ldivisor;
long multiple = 1;
while ((sum+sum) <= ldividend) {
sum += sum;
multiple += multiple;
}
//Look for additional value for the multiple from the reminder (dividend  sum) recursively.
return multiple + ldivide(ldividend  sum, ldivisor);
}
Clean Java solution with some comment.


Nice explanation with good selfdescriptive identifiers. This solution shows that every number can be represented as sum of powers of 2 which is somewhat similar to how binary search works .
Also , no need to return Integer.MIN_VALUE since problem statement says return MAX_INT in case of overflow.

In java, Integer.MAX_VALUE is a builtin static parameter representing 2^311. Problem asks you to return max integer value, describing in a programming language way of saying 'MAXINT', MAXINT is not a instance variable which has already been put in Solution Class so returning MAXINT will cause compile error.

Nice solution. Here is my shorter and easier to understand code.
Hint:

The divisor will never be 0.

Make the divisor as big as possible.

long to int, narrow down the range and then convert.
public class Solution {
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
boolean neg = (dividend < 0) ^ (divisor < 0);
long m = Math.abs((long)dividend), n = Math.abs((long)divisor);
long result = 0;
while (m >= n) {
int shift = 0;
while (m > (n << shift + 1)) {
shift++;
}
m = n << shift;
result += (1 << shift);
}
result = (neg) ? ~(result  1) : result;
result = Math.min(Integer.MAX_VALUE, result);
result = Math.max(Integer.MIN_VALUE, result);
return (int)result;
}
}


thanks for sharing! we are on the same track, yet i think my code is shorter and clearer:
/*  possible overflow: Integer.MIN_VALUE / (1); anything / 0. */ public class Solution { public int divide(int dividend, int divisor) { if (divisor == 0  dividend == Integer.MIN_VALUE && divisor == 1) return Integer.MAX_VALUE; int sign = (dividend ^ divisor) >> 31; int quotient = divideHelper(Math.abs(Long.valueOf(dividend)), Math.abs(Long.valueOf(divisor))); return sign == 0 ? quotient : quotient; } private int divideHelper(long top, long bot) { if (top < bot) return 0; long cur = bot; int count = 1; while (cur <= (top >>> 2)) { cur <<= 1; count <<= 1; } count += divideHelper(top  cur, bot); return count; } }

Keep substracting divisor and double it each time. Whenever you overshoot and divisor goes more than dividend, go back to previous value, and try again.
public int divide(int a, int b) { if(a==Integer.MIN_VALUE){ if(b==1) return Integer.MAX_VALUE; } long x = a < 0 ? (long)a : (long)a; long y = b < 0 ? (long)b : (long)b; int res = recurse(x, y, 1); if(a < 0 && b < 0) return res; if(a < 0  b < 0) return res; return res; } public int recurse(long x, long y, int count) { if(x <= 0  count==0) return 0; if(y > x) return recurse(x, y >>> 1, count >>> 1); //overshot, so divide and try again. else return recurse(xy, y+y, count+count)+count; }


public class Solution {
public static int divide(int dividend, int divisor) {
if(divisor==0dividend==Integer.MIN_VALUE&&divisor==1) return Integer.MAX_VALUE;
if(divisor==1) return dividend;
int sign=((dividend>0)^(divisor>0))?1:1;
long did=Math.abs((long)dividend);
long div=Math.abs((long)divisor);
int res=0;
while(did>=div){
long tmp=div;
int mutiple=1;
while(did>=(tmp<<1)){
tmp<<=1;
mutiple<<=1;
}
did=tmp;
res+=mutiple;
}
return sign==1?res:res;
}
}

@sixgod Suppose you use Math.abs() for Integer.MIN_VALUE. The absolute value of Integer.MIN_VALUE would overflow if not use long type.

@jaqenhgar Hello , I find out that in your solution when I change
if(x <= 0  count==0) return 0;
intoif(x == 0  count==0) return 0;
,it also works well and even faster. So is there any reason why you choose the first one?

Thank you @jinwu for your idea. I think your implementation can be simplified.
Your idea is mainly based on long division.
Here is the simplified implementation based on long division:public int divide(int dividend, int divisor) { if (divisor == 0  (dividend == Integer.MIN_VALUE && divisor == 1)) return Integer.MAX_VALUE; // idea similar to "long division" int sign = (dividend > 0) ^ (divisor > 0) ? 1 : 1;// XOR to determine same sign? long ldividend = Math.abs((long)dividend); long ldivisor = Math.abs((long)divisor); long multiple = 1; long ans = 0; // STEP 1: shift "divisor" to the most siginificant bit while ((ldivisor << 1) <= ldividend) { multiple <<= 1; ldivisor <<= 1; } // STEP 2: shift right to perform "long division" while (multiple > 0) { if (ldividend >= ldivisor) { ldividend = ldivisor; ans += multiple; } multiple >>= 1; ldivisor >>= 1; } return sign == 1 ? (int)ans : (int)ans; }