题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

样例

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

算法1

(模拟 + 倍增) $O(logn)$

如果全程只能使用int，这道题还是挺蛋疼的；
将被除数和除数都转换成负数做，避免正数域比负数域小，造成一些奇怪的现象；
倍增过程见代码。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int divide(int a, int b) {
        // corner case
        if (a == INT_MIN && b == -1) return INT_MAX;
        if (a == 0) return 0;

        // 初始化
        const int limit = -1073741824;
        int res = 0, sign = (a > 0) ^ (b > 0) ? 1 : -1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;

        // 倍增求解
        while (a <= b){
            int tmp = b, m = -1;
            while (tmp >= limit && m >= limit && tmp + tmp >= a){
                tmp += tmp;
                m += m;
            }

            a -= tmp;
            res += m;
        }

        return sign * res;
    }
};

$JAVA$

class Solution {
    public int divide(int a, int b) {
        if (a == 0) {
            return 0;
        }

        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        int res = 0, sign = (a > 0) ^ (b > 0) ? 1 : -1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;

        int limit = Integer.MIN_VALUE >> 1;
        while (a <= b) {
            int tmp = b, m = -1;
            while (tmp >= limit && m >= limit && tmp + tmp >= a) {
                tmp += tmp;
                m += m;
            }

            a -= tmp;
            res += m;
        }

        return sign * res;
    }
}