题目内容

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

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示

1、被除数和除数均为 32 位有符号整数。
2、除数不为 0。
3、假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

题解

本题是一道利用加减法实现除法运算。假设x/y=k，那么有如下思考：

1、若将k修改为二进制表示，假设为1101，那么，可得x = ky = ($2^3$+$2^2$+$2^0$)y。让我们思考一下，如果不用表示，x应该需要减掉k次y得到答案，但是如果将k使用二进制表示，x就可以减去logk次的y。又由于题目中有数值范围限制，因此最多x只会减去31次$2^n$y(0≤n≤31)，这样就将减去的次数调整为常数级别。

2、在判断x应该减去哪些$2^n$y的过程中就把商的二进制表示求出来了。具体可以这样思考：因为如果x/y>$2^{30}$，就说明x>$2^{30}$y，因此商二进制表示的第30位为1，也就表示x就需要减去$2^{30}$y；当然，如果x/y>$2^{30}$，说明x<$2^{30}$y，因此x就不需要减去该项，商的二进制表示的第30位就为0。上述这种判断直到把全部应该减去的$2^n$y部分剪完，也就求出来k的二进制表示了，然后再进一步求出k的十进制的值即可。

3、本题中涉及到的乘法要使用加法代替，涉及到的除法要使用减法代替

具体，请看代码注释

代码

class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;//首先，因为两个整数相除存在溢出的问题，比如-2^31 / -1 = 2^31，超过整型最大值。因此采用long long类型避免了程序报错。如果题目不让，再进行判断处理。
        vector<LL> exp;//定义y*2^n的值的数组
        bool is_minus = false;
        if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;//判断正负号标志

        LL a = abs((LL)x), b = abs((LL)y);//全部强制类型转化为long long型
        for (LL i = b; i <= a; i = i + i) exp.push_back(i);//将y*2^n的值计算出来

        LL res = 0;
        for (int i = exp.size() - 1; i >= 0; i -- )
          	//如果a也就是x  大于 对应的y*2^n，就减掉，然后商的第i位为1，直接使用左移运算符，计算出2的^i次方
            if (a >= exp[i]) {
                a -= exp[i];
                res += 1ll << i;//通过找出商的二进制表示，这里直接求出res的十进制的值。每找到某位为1，直接求出对应2的i次方的值，然后全部相加得出
            }

        if (is_minus) res = -res;//如果除数或者被除数有负数，则商一定为负

        if (res > INT_MAX || res < INT_MIN) res = INT_MAX;//这里判断溢出，即大于最大int值或者小于最小int值，返回题目要求的最大int值。

        return res;
    }
};