题意：给定除数和被除数，要求不使用乘法、除法、取余求商，只保留整数。运行环境的整数范围在32位以内，如果商超过最大/小值就返回最大/小值。

29. Divide Two Integers (opens new window)

题目要求不能用乘法、除法和取余，剩下加减法，可能会想到用被除数不停的减去除数实现，但是时间复杂度太高了。例如2147483647和1，需要循环2147483647次减法，效率太低。

上面的算法是线性阶，那么有没有对数阶的算法呢？本题可以抽象为如何把除数更快速的接近被除数，因为乘法被禁用，就只剩下位运算了，左移相当于乘以2。

因为题目要求运算环境不能溢出，所以处理过程中还需要注意以下几点：

• -2147483648和-1，因为最大值是2147483647，结果会溢出，需要特殊处理。
• 为了方便操作，把被除数和除数转为负数，最后返回时带上符号。为什么不是正数？因为被除数为-2147483648时，转成正数就溢出了，反过来则不会。
• 左移时要注意不能溢出，需要提前计算能左移次数的最大值。

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        // 是否为负数
        boolean negative = (dividend < 0) ^ (divisor < 0);
        // 取负数
        dividend = dividend < 0 ? dividend : -dividend;
        divisor = divisor < 0 ? divisor : -divisor;
        // 因为是负数，如果被除数比除数大，直接返回0
        if (dividend > divisor) {
            return 0;
        }
        int quotient = 0;
        int max = findShiftLeftMax(dividend, divisor);
        while (dividend <= divisor) {
            int cnt = 0;
            // 左移次数限制，防止溢出
            while (cnt <= max && max > 0 && dividend - (divisor << cnt << 1) <= 0) {
                cnt++;
            }
            if (cnt > max) {
                cnt = max;
            }
            quotient += 1 << cnt;
            dividend -= divisor << cnt;
        }
        return negative ? -quotient : quotient;
    }

    private int findShiftLeftMax(int dividend, int divisor) {
        int half = dividend >> 1;
        int max = 0;
        while (divisor >= half) {
            divisor = divisor << 1;
            max++;
        }
        return max;
    }
}