29. 两数相除

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        // 用异或来计算是否符号相异，并记录下来
        boolean negative = (dividend ^ divisor) < 0;
        // 将两数变为正数来进行接下来的处理
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        int res = 0;
        // 计算由a可以由多少个b相加而得
        for (int i = 31; i >= 0; i--) {
            // 找到足够大的2^n 个 b
            if ((a >> i) >= b) {
                // 将结果加上 2^n
                res += 1 << i;
                // a 减去 2^n * b
                a -= b << i;
            }
        }
        return negative ? -res : res;
    }
}

• 时间复杂度 O(1)
• 空间复杂度 O(1)