Divide Two Integers

Problem

Divide Two Integers

Approach

1. The easiest way is to minus the dividend by divisor as many times as possible. No doubt that it will fail and get TLE.
2. Then, we have to cut down the time of subtraction. So, we can try to make the divisor to be bigger.
3. Firstly, let’s get the digit that means after some bitwise operations, the divisor becomes to the biggest one but smaller than dividend.
4. After get the digit, we can simulate the division step by step.

Code

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        int flag = 1;
        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)){
            flag = -1;
        }
        long dvd = Math.abs((long)dividend);
        long dsr = Math.abs((long)divisor);
        int digit = 0;
        while(dsr << 1 <= dvd){
            dsr <<= 1;
            digit ++;
        }
        int ans = 0;
        while(digit >= 0){
            if(dvd >= dsr){
                dvd -= dsr;
                ans += 1 << digit;
            }
            digit --;
            dsr >>= 1;
        }
        if(flag == -1){
            ans = -ans;
        }
        return ans;
    }
}