算法思路

该题目要求返回两个数相除下取整的结果，但是要求不使用乘法、除法和 mod 运算符。都知道乘法是求相同的几个数相加，那么反过来除法就是求被除数里面最多有几个除数。因此一个直观的想法就是利用减法，每次减去除数，直到被除数减为零或减到小于除数时，减去的除数个数即为相除结果。

但是该方法如果在被除数很大，而除数很小时，时间复杂度会非常高，以此题为例，题目中被除数和除数范围均在$[−2^{31}, 2^{31} − 1]$中，当被除数取最大，除数为1时，结果会约等于$2^{31}$,如果选择每次减1，则最终时间复杂度会达到上亿级，因此我们需要对算法进行优化。

这里我们优化的方法是利用倍增和贪心的思想，具体思路如下：

1. 倍增
当我们对除数做减法时，一个一个减必然会花费大量的时间，如果每次我们减去一个更大的数，时间必然会减少，例如如果x = 100, y = 1,计算x / y,那么我们需要减100次，当x = 100, y = 2,我们需要减50次,而如果x = 100, y = 4我们就只需要减25次。因此我们每次做减法的时候，如果可以每次减去一个大于除数的倍数，那么我们的时间复杂度必然能够得到优化，同时该除数的倍数大小即为一次性减去的该除数的个数。

2. 贪心
利用贪心的思路，如果我们每次减去的数越大，那么我们做减法的次数就会越少，我们的时间复杂度也就会越低。因此在每次做减法时，我们需要找到小于被除数的最大的除数的倍数。每次用被除数减去该最大的倍数，同时答案加上该倍数值，直到被除数小于除数。

注意：

1. 该题目中还有一些细节，题目要求如果除法结果溢出，则返回 $2^{31} − 1$,因为被除数最小可以取到$-2^{31}$,当除数为$-1$时，结果为$2^{31}$，即溢出了，因此此时需要进行特判。

2. 在进行减法时，我们需要先求出最终结果的符号，然后将被除数和除数转化为正数后，然后再进行减法运算。因此，虽然当被除数取到$-2^{31}$时，除法结果不一定溢出，但是此时它的绝对值溢出了，所以在计算时我们需要用一个更大的变量表示该被除数或除数的绝对值。

C ++代码

class Solution {
public:
    int divide(int x, int y) {
        if (x == INT_MIN && y == -1) {
            return INT_MAX; //如果除法溢出，返回2 ^ 31 - 1
        }
        long a = labs(x), b = labs(y), ans = 0;
        int sign = x > 0 ^ y > 0 ? -1 : 1;

        while (a >= b) { //当a比b大，说明a/b至少等于1
            long temp = b, m = 1;
            while (temp << 1 <= a) { //找到最大的小于被除数的除数倍数
                temp <<= 1; //除数倍增
                m <<= 1; //减法个数倍增
            }
            a -= temp; //除数变小
            ans += m; //加上个数
        }
        ans *= sign;
        return ans;
    }
};