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

If it is overflow, return MAX_INT.

Hint:

1. The divisor will never be 0.
2. Make the divisor as big as possible.
3. long to int, narrow down the range and then convert.

The thinking behind this problem is to use bit manipulation, as some operators are prohibited in the question.

Source

class Solution {
    public int divide(int dividend, int divisor) {
        int res=0;
        if(dividend==Integer.MIN_VALUE&divisor==-1||divisor==0) return Integer.MAX_VALUE;
        // handle overflow situations
        // 1. divisor = 0
        // 2. dividend is MIN_VAL and divisor is -1, (because abs(INT_MIN) = INT_MAX + 1).
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        // chech if the sign of both divdend and divisor is the same

        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);
        // use long type to avoid possible overflow when shifting

        while(dvd>0){
            long cnt=1;
            long div=dvs;
            while(dvd>=div){
                div<<=1;
                cnt<<=1;
            }
            // find the biggest possible divisor *2,*4,*8
            // subtract from the dividend and continue
            res+=(cnt>>1);
            dvd-=(div>>1);
        }
        return (sign>0)?res:-res;
        // add back the sign
    }
}