29. Divide Two Integers (Medium)

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

If it is overflow, return MAX_INT.

Solution: Math, Binary Search, Bit Manipulation

class Solution {
public:
    int divide(int dividend, int divisor) {
        // overflow
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) 
            return INT_MAX;

        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1:1;
        long dvd = labs(dividend), dvs = labs(divisor);
        int res = 0;
        while (dvd >= dvs) {
            long tmp = dvs, multiple = 1;
            while (dvd >= (tmp << 1)) {
                tmp <<= 1;
                multiple <<= 1;
            }
            dvd -= tmp;
            res += multiple;
        }

        return sign == 1 ? res: -res;
    }
};