At first, I used dividend / divisor, just to check. But that was cheating.

Then, I implemented a solution which failed the corner cases. I solved it by using long instead of int. But I felt that was also cheating.

At last, I came up with this solution. It handles all the corner cases. Running time analysis after the code.

```
public class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 1) // Trival case 1
return dividend;
// Use negative integers to avoid integer overflow
if (dividend > 0)
return -divide(-dividend, divisor);
if (divisor > 0)
return -divide(dividend, -divisor);
if (dividend > divisor) // Trivial case 2
return 0;
if ((dividend == Integer.MIN_VALUE) && (divisor == -1)) // Overflow case
return Integer.MAX_VALUE;
// Find the highest mult = (divisor * 2^shifts) which is <= dividend
// by shifting mult to the left without causing an overflow.
// At most (log2(|dividend|) - log2(|divisor|) + 1) iterations.
int min_divisor = Integer.MIN_VALUE >> 1;
int mult = divisor; // = divisor * 2^shifts
int shifts = 0;
while ((mult >= min_divisor) && (mult > dividend)) {
mult <<= 1;
++shifts;
}
// Compute the result by shifting mult to the right.
// At most (log2(|dividend|) - log2(|divisor|) + 1) iterations for the outer loop.
// At most (log2(|dividend|) - log2(|divisor|) + 1) iterations for the inner loop
// (in total, not per outer iteration).
int result = 0;
int power = 1 << shifts; // = 2^shifts
while (dividend <= divisor) {
shifts = 0;
while (mult < dividend) {
mult >>= 1;
++shifts;
}
dividend -= mult;
power >>= shifts;
result |= power; // Adds power to result
}
return result;
}
}
```

I see lots of people talking about O(log(n)) solutions. Since n is bounded by -2^31 and 2^31-1, I'm not sure the Big-Oh notation is appropriate here. Anyway, here's a rough worst-case analysis of this code.

The first loop runs (log2(|dividend|) - log2(|divisor|) + 1) times. There are

- 2 comparisons
- 1 bit shift
- 1 increment

The second loop runs between 1 time and (log2(|dividend|) - log2(|divisor|) + 1) times. For worst-case, we take the latter. There are

- 1 comparison
- 1 assignment
- 1 substraction
- 1 bit shift
- 1 bitwise or

The inner while loop runs (log2(|dividend|) - log2(|divisor|) + 1) times also (in total, not per outer loop iteration). There are

- 1 comparison
- 1 bit shift
- 1 increment

So, roughly, the overall worst-case running time is 12(log2(dividend) - log2(divisor) + 1) operations. You can notice that (log2(|dividend|) - log2(|divisor|)) = log2(|result|). Thus, the running time is (worst-case) 12(log2(|result|) + 1) operations.