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

## Analysis

We can keep subtract divisor from dividend until dividend is smaller than 0, than count the subtract numbers. But it will costs a very long time if the divisor is very small comparing to dividend.

Shift can be used to solve this problem. We shift the divisor left until it just smaller than dividend but if we keep shifting one more bit, it’s larger than dividend. Than we can add the shifted value to the result and subtract the shifted value from dividend. Keep doing this until dividend is smaller than divisor. In fact, every integer can be represented by a set of base 2 so that shifting can be used.

One thing needs to be mentioned is that we need to convert the integer to long type. Otherwise the Math.abs() value of Integer.MIN_VALUE will be quite strange.

## Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class Solution { public int divide(int dividend, int divisor) { long p = Math.abs((long)dividend); long q = Math.abs((long)divisor); int ret = 0; while (p >= q) { int counter = 0; while (p >= (q << counter)) { counter++; } ret += 1 << (counter - 1); p -= q << (counter - 1); } if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) return ret; else return -ret; } } |

Updated on March 7th, 2015. Add the following code to pass the corner case. Not sure if it is the best way.

1 2 |
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; |

## Complexity

The complexity is O(log n).