Leetcode.29

class Solution {
public:
    int divide(int x, int y) {
        // 特判：如果除法溢出，返回2 ^ 31 - 1；只有这种情况ans会溢出
        if (x == INT_MIN && y == -1) return INT_MAX; 
        long a = abs(x), b = abs(y), ans = 0;
        int sign = x < 0 ^ y < 0 ? -1 : 1;

        while (a >= b) {        // 保证被除数>=除数，ans起码有1
            long tmp = b, m = 1;
            while (tmp << 1 <= a) {  // 找到最大的小于被除数的除数倍数值
                tmp <<= 1;           // 除数倍增
                m <<= 1;             // 减法次数倍增---答案
            }
            a -= tmp;                // 被除数减小
            ans += m;                // 答案增加
        }
        ans *= sign;
        return ans;
    }
};