[数据结构与算法]01-整数除法

整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231?1]。本题中，如果除法结果溢出，则返回 231 ? 1
 
示例 1：
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：
输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：
输入：a = 0, b = 1
输出：0

示例 4：
输入：a = 1, b = 1
输出：1

class Solution {
    public int divide(int a, int b) {
    	// 避免被除数是最小值时溢出
        if(a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

		// 判断商的正负
        boolean flag = false;
        if((a > 0 && b < 0) || (a < 0 && b > 0)) {
            flag = true;
        }
		
		// 讲被除数和除数都转换为负数进行运算避免溢出
        if(a > 0) {
            a = -a;
        }

        if(b > 0) {
            b = -b;
        }

        int ans = 0;
        // 因为a b都是负数 所以 a <= b 表示 |a| >= |b|
        while(a <= b) {
            int tmp = b;
            int k = 1;
			// 找到当前 a 最多可以减去的 b 的个数
			// 因为tmp也是负数 所以 >= 实际上是绝对值 <= 
			// tmp >= 0xc0000000防止越界 0xc0000000是最小值的一半
            while(tmp >= 0xc0000000 && a <= tmp + tmp) {
                k = k + k;
                tmp = tmp + tmp;
            }
            ans += k;
            a -= tmp;
        }

        return flag ? -ans : ans;
    }
}