题目链接：https://leetcode.cn/problems/divide-two-integers/

解题思路：因为不能使用乘法，除法和取余运算，所以可以使用加法和减法来做除法，商的结果就是被除数是除数的几倍，即有多少个除数

1. 比较容易想到的是每次让被除数减去除数，直到被除数小于除数，然后一共减了多少次即所求商，每次减去一个除数，太慢了，还有更有的解法：依次减去除数的一倍，二倍，四倍，八倍....，使用result保存结果，result依次加1，加2，加4，加8...，如果当前减去的除数的倍数大于被除数的一半，就反过来，依次减去除数的，...，八倍，四倍，二倍，一倍，result依次加...，加8，加4，加2，加1。这样每次可以成倍的减去除数，计算速度更快。

1. 解释：为什么成倍的加最终可以得到正确的答案

被除数除以除数的商可能是任意的数字，1，2，3，...

而result是成倍的加的，为什么会得到最终正确的答案呢？

注意，result每次加的可能取值为1，2，4，8，16，...，可以用这些数相加组合成任意一个自然数，比如如果最终的结果为3，则为1+2，最终的结果为7，则为1+2+4

因此，成倍的加最终依然可以得到正确的答案，而且效率更高！

2. 又因为环境只能存储32位的有符号整数，可能会发生溢出情况，即int的最小值-2147483648除以-1时等于2147483648发生了溢出，而被输出和除数的符号组合有四种情况，为了减少判断的逻辑，可以将被除数和除数的符号相等，都为正数或者负数，而负数转正数的时候，可能会发生溢出，因此将被除数和除数都转为负数，只需要记录最终结果的正负号就可以了，即被除数和除数的最高符号位进行异或运算，如果结果为1，即，被除数和除数异号，最终商应为负数，否则，商为正数

具体算法流程如下：

1. flag = ((dividend >>> 31) ^ (divisor >>> 31)) == 1 ? -1 : 1，flag保存最终结果的符号

2. 将被除数和除数都转为负数

3. 初始条件，tem=divisor，add=1，result=0（add表示当前减去几倍的除数）

4. 如果tem大于等于被除数的一半，循环执行：

1. divided-=tem

2. result+=add

3. tem<<=1(除数依次扩大一倍)

4. add<<=1

5. 如果上述循环结束时，divided<=divisor(因为被除数和除数都是负数，说明被除数还可以继续减去除数)则循环执行：

1. 如果tem

1. tem>>=1

2. add>>=1

2. divided-=tem

3. result+=add

4. tem>>=1(除数依次减少一倍)

5. add>>=1

6. 因为每次result加的都是一个正数，而对于-2^31/-1会发生正数溢出，而此时result加了-1的2^31倍，大于整数的最大值(2^31-1)，这种情况下result的结果为-2^31，如果最终商的结果为正数，此时应该返回2^31-1，而对于其他情况-2^31/1和2^31/-1，这种情况下，最终计算的时候依然时使用-2^31/-1进行计算的，此时结果-2^31就是正确答案，所以直接返回result即可

AC代码

class Solution {public static int divide(int dividend, int divisor) {int flag = ((dividend >>> 31) ^ (divisor >>> 31)) == 1 ? -1 : 1;if (dividend > 0)dividend = -dividend;if (divisor > 0)divisor = -divisor;int add = 1;int tem = divisor;int result = 0;while (tem >= dividend>>1) {dividend -= tem;result += add;add <<= 1;tem <<= 1;}while (dividend <= divisor) {while (tem < dividend) {tem >>= 1;add >>= 1;}dividend -= tem;result += add;tem >>= 1;add >>= 1;}if (result == Integer.MIN_VALUE&&flag == 1){result = Integer.MAX_VALUE;}return result*flag;}
}