1. 题目描述

题目链接
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 −231 ，则返回 −231。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333… ，向零截断后得到 3 。

示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333… ，向零截断后得到 -2 。

2. 思考

这题的本质是用加/减法表示除法，考虑到输入的被除数和除数可能出现异号的情况。如果两数异号，那么除法应该转化为加法，比如-7 / 3 = -2.333，按照本题意义答案为-2，相当于在被除数-7上加了2个除数2，答案取反；而同号时，比如-7 / -3 = 2.333，答案取2，可以看做在被除数-7上减了两个除数-3，答案取正。
那么我们需要统一处理一下，可以考虑将被除数与除数都变成同号，这样只需要让被除数不断地减去除数即可。但要记录一下原来两个数是否异号，若异号那么答案需要取反：

bool neg = (dividend >> 31) ^ (divisor >> 31);
return neg ? -ans : ans;

那么究竟是都变为正，还是都变为负呢？考虑INT_MIN = −231，如果这个数取正会发生溢出，相反，对INT_MAX取负就不会，因此我们考虑把被除数与除数均变为负数：

// 均变为负数，一是防止异号，二是负变成会导致溢出（INT_MIN变为正会溢出）
if (dividend > 0) dividend = -dividend;
if (divisor > 0) divisor = -divisor;

然后我们考虑如何模拟除法。首先想到可以不断让被除数减去除数，直到结果大于除数（对于正数，应该是直到结果小于除数，负数则正好相反，比如-7减去两个-3结果为-1，比-3大，计算结束）。但是如果除数很小，一个一个减未免太浪费时间，因此考虑不断让除数倍增，直到除数小于被除数一半为止，此时再倍增除数会导致除数小于被除数，也就是被除数大于除数，这以后的倍增都是不应该考虑的（前面已经说过，如果被除数大于除数，计算结束）。在这个过程中记录当前除数是原始除数的倍数（该倍数随着除数一起倍增）。

//mod是当前除数，times是mod相对原始除数的倍数
int times = -1, mod = divisor;
int half_dividend = dividend >> 1;
while (mod >= half_dividend) {
    mod <<= 1;
    times <<= 1;
}

在上面这个操作之后，我们得到最小的除数（再小就不行了！），此时判断被除数是否小于等于当前除数mod，是则让被除数减去mod（同时答案减去倍数times），然后将mod缩小2倍（与倍增方向相反），之后判断剩余被除数是否仍小于等于原始除数，若是则重复上述操作，不是则结束计算，根据neg标记对答案进行取正取反。

int ans = 0;
while (dividend <= divisor) {
    if (dividend <= mod) {
        dividend -= mod;
        ans -= times;
    }
    mod >>= 1;
    times >>= 1;
}

这样做能得到正确答案的原因是，将mod从大到小想象成2k到20倍的原始除数，最后得到的商一定是这些2的倍数的组合，而且每个最多使用一次！因为这些倍数就对应着商的二进制表示每一位：20代表第0位，21代表第1位……。比如，32 / 5 = 6，这里商是6，也就是6个除数5，6表示为二进制是110，而按照上述计算过程，被除数减去的mod依次为-20和-10，剩余的-2因为大于原始除数-5，因此计算结束。减去的mod分别是除数-5的22 = 4和21 = 2倍，所以最终商的二进制表示中，只有第2和第1位为1。
按照力扣官方解答，其实可以用用数组来存放每个2的倍数倍的除数，然后倒序减，直到结果大于原始除数。这里使用的方法是一致的，不过省去了数组（因为每个当前除数mod最多用一次，就像一个数的二进制为最大为1）。

##3. 代码实现
除了上述基本计算方法外，这里注意处理一点特殊情况，即被除数为INT_MIN，而除数为1或-1的情况

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN) {
            if (divisor == 1) return INT_MIN;
            else if (divisor == -1) return INT_MAX;
        }
        bool neg = (dividend >> 31) ^ (divisor >> 31);
        // 均变为负数，一是防止异号，二是负变成会导致溢出（INT_MIN变为正会溢出）
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        int times = -1, mod = divisor;
        int half_dividend = dividend >> 1;
        while (mod >= half_dividend) {
            mod <<= 1;
            times <<= 1;
        }
        int ans = 0;
        while (dividend <= divisor) {
            if (dividend <= mod) {
                dividend -= mod;
                ans -= times;
            }
            mod >>= 1;
            times >>= 1;
        }
        return neg ? -ans : ans;
    }
};