[数据结构与算法]整数除法（不用*，/，％）

一、题目

二、思路??

????????由于题目规定了「只能存储 32 位整数」，代码中都不会使用任何 64位整数。诚然，使用 64?位整数可以极大地方便我们的编码，但这是违反题目规则的。

????????如果除法结果溢出，那么我们需要返回-1?作为答案。因此在编码之前，我们可以首先对于溢出或者容易出错的边界情况进行讨论：

• 当被除数为 32?位有符号整数的最小值-时：
  • 如果除数为 1，那么我们可以直接返回答案?-?；
  • 如果除数为 ?1，那么答案为 ，?，产生了溢出。此时我们需要返回 - 1。
• 当除数为 32 位有符号整数的最小值 -? 时：

  • 如果被除数同样为 ?-?，那么我们可以直接返回答案 1；

  • 对于其余的情况，我们返回答案 0。

• 当被除数为 0?时，我们可以直接返回答案 0

????????对于一般的情况，根据除数和被除数的符号，我们需要考虑 4 种不同的可能性。因此，为了方便编码，我们可以将被除数或者除数取相反数，使得它们符号相同。

????????如果我们将被除数和除数都变为正数，那么可能会导致溢出。例如当被除数为-? 时，它的相反数，? 产生了溢出。

????????因此，我们可以考虑将被除数和除数都变为负数，这样就不会有溢出的问题，在编码时只需要考虑 1 种情况了。

????????如果我们将被除数和除数的其中（恰好）一个变为了正数，那么在返回答案之前，我们需要对答案也取相反数。

2.1、二分法

????????根据「前言」部分的讨论，我们记被除数为 X，除数为 Y，并且 X?和 Y都是负数。我们需要找出 X/Y的结果 Z。Z?一定是正数或 0。

????????根据除法以及余数的定义，我们可以将其改成乘法的等价形式，即：
????????????????????????????????????????????????????????Z×Y≥X>(Z+1)×Y

????????因此，我们可以使用二分查找的方法得到 Z，即找出最大的 Z?使得Z×Y≥X 成立。

????????由于我们不能使用乘法运算符，因此我们需要使用「快速乘」算法得到 Z×Y 的值。

class Solution {
    public int divide(int a, int b) {
        // 考虑被除数为最小值的情况
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            }
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (b == Integer.MIN_VALUE) {
            return a == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (a == 0) {
            return 0;
        }
        
        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (a > 0) {
            a = -a;
            rev = !rev;
        }
        if (b > 0) {
            b = -b;
            rev = !rev;
        }
        
        int left = 1, right = Integer.MAX_VALUE, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            int mid = left + ((right - left) >> 1);
            boolean check = quickAdd(b, mid, a);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == Integer.MAX_VALUE) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    public boolean quickAdd(int y, int z, int x) {
        // x 和 y 是负数，z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}

??