Leetcode 29. Divide Two Integers

Divide Two Integers.

The core observation in my solution is for any number n, n << 1 == n * 2 (with the assumption that there is no overflow.)

So for this problem, we can multiply the divisor by 2 using the shift operation until the ABS of dividend is smaller than the ABS of the divisor. The subtract the multiply result from the dividend, record what you have subtracted.

There are a few traps you need to pay attention to though.

  • First, result can be overflow if dividend is Int32.MinValue and divisor is -1.
  • Second, be careful with the sign of the numbers, I convert all numbers to positive before doing actual calculation.
  • Third, Shift right operation in signed integer number will have the left most digit retained, in this problem, you need to use unsigned integer instead.
public class Solution {
    public int Divide(int dividend, int divisor) {
        if(dividend == Int32.MinValue && divisor == -1) return Int32.MaxValue;
        if(divisor == Int32.MinValue && dividend != divisor) return 0;
        if(dividend == divisor) return 1;
        int sign = 0;
        int res = 0;
        if(divisor < 0) { divisor = -divisor; sign += 1; }
        if(dividend == Int32.MinValue) { dividend += divisor; res +=1; }
        if(dividend < 0) { dividend = -dividend; sign += 1; } 
        while(dividend >= divisor){
            uint b = 1;
            uint multidiv = (uint)divisor;
            while(((uint)dividend) >= multidiv){
                b <<= 1;
                multidiv <<= 1; } b >>= 1;
            multidiv >>= 1;
            res += (int)b;
            dividend -= (int)multidiv;
        }
        if(sign % 2 == 0) return res;
        else return -res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *