Divide Two Integers Medium
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
public int divide(int dividend, int divisor) { if (divisor == 0) throw new java.lang.ArithmeticException("/ by zero"); long result = divideLong(dividend, divisor); return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result; } public long divideLong(long dividend, long divisor) { boolean negative = dividend < 0 != divisor < 0; if (dividend < 0) dividend = -dividend; if (divisor < 0) divisor = -divisor; if (dividend < divisor) return 0; long sum = divisor; long divide = 1; while ((sum + sum) <= dividend) { sum += sum; divide += divide; } return negative ? -(divide + divideLong((dividend - sum), divisor)) : (divide + divideLong((dividend - sum), divisor)); }思路：模拟除法，每次被除数(dividend)加倍，则除的结果加倍（从1开始，2、4、8……）。O((lgn)^2)
除数/被除数=结果，根据等式原理，两边同时乘以相同数仍然相等。例：
55/5 = 11
每次加倍，所以5->10->20->40 (对应结果1->2->4->8)，注意1*5=5, 2*5=10, 4*5=20, 8*5=40
