[数据结构与算法]LeetCode-100题(Hot) 29. 两数相除 [Java实现]

给定两个整数，被除数?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

很朴素的一题?如果没有 0x80000000 的话。 那么在题设条件下我们需要先注意到一个关键点：

32 位有符号整数，其数值范围是 [?2^31,? 2^31?? 1]

即单从绝对值来看最小值比最大值的绝对值大1，那么为了防止 int 类型数据溢出，我们不妨将除数与被除数都转化为整数进行处理：

    public int divide(int dividend, int divisor) {
        // 处理特殊情况: 规定 -2^31 / -1 = 2^31
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean positive = (dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0);
        int negDividend = dividend > 0 ? -dividend : dividend;
        int negDivisor = divisor > 0 ? -divisor : divisor;
        int result = 0;
        while (negDividend <= negDivisor) {
            negDividend -= negDivisor;
            result ++;
        }
        return positive ? result : -result;
    }