Divide Two Integers

Quesiton from: https://leetcode.com/problems/divide-two-integers/

题目：

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

If it is overflow, return MAX_INT.

---

题目分析：

• Integer Overflow, 边界处理, special case:
  • x/0
  • Integer.MIN_VALUE/(-1)
• Bit Operation
• O(logn) runtime
• Attention on Line #39, (num1 >>1) 可以防止 num2 overflow。

面试里，尽量不要使用 long 来处理 Integer Overflow。因为这道题目本身考查的就是各种 Corner Cases 的处理。

public int divide(int dividend, int divisor) {
    if(divisor == 0) {
        return Integer.MAX_VALUE;
    }
    
    if(dividend == 0) {
        return 0;
    }
    
    if(divisor == Integer.MIN_VALUE) {
        return (dividend == divisor)?1:0;
    }
    
    int sign = (((dividend^divisor) >> 31) == 0)? 1:-1;
    int res = 0;
    int num1 = 0;
    int num2 = Math.abs(divisor);
    
    
    if(dividend == Integer.MIN_VALUE) {
        if(divisor == -1) {
            return Integer.MAX_VALUE;
        } else {
            res = 1;
            num1 = Math.abs(dividend + num2);
        }
    } else {
        num1 = Math.abs(dividend);
    }
    
    res = helper(num1, num2, res);
    
    return (sign>0)?res:-res;
}

private int helper(int num1, int num2, int res) {     
    int times = 1;

    while(num2 <= (num1>>1)) {
        num2 = num2<<1;
        times = times<<1;
    }
    
    while(times > 0) {
        if(num1 >= num2) {
            num1 -= num2;
            res += times;
        }
        times >>= 1;
        num2 >>= 1;
    }
    
    return res;
}