这题看似简单，实则一点也不难（不是），实则还是比较困难。
最简单的做法是直接用减法，不停循环计数，最后统计减多少次能成。
如果被除数是2^31-1或差不多大小的数，而除数是1差不多大小的数，那循环减法要执行的次数太多，一定会超时。
所以一定要有更好的思路
（1）通过二分法查找可能的商
（2）对于每一个可能得商，跟除数相乘，然后跟被除数比大小，根据大小关系来决定商应该去左边区间还是右边区间。这里不能直接用乘法，所以得用类似于二进制竖式的方式，快速通过加法结合位移运算实现“快速乘法”
还有一些细节上的难点，代码注释中写得很清楚。
class Solution {
public int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
}
if (divisor == -1) {
return Integer.MAX_VALUE;
}
}
// 考虑除数为最小值的情况
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}
// 一般情况，使用二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
boolean rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}
//divisor绝对值至少也是1，因此商不可能比dividend的绝对值大，因此right初始值设为-dividend即可
//（大部分情况下-dividend要比Integer.MAX_VALUE小，因此能节约时间）
//但是dividend有可能为Integer.MIN_VALUE,这时right设为
//int left = 1, right = Integer.MAX_VALUE, ans = 0;
int left = 1, right = dividend==Integer.MIN_VALUE?Integer.MAX_VALUE:-dividend, ans = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
//true表示divisor * mid >= dividend,此时应该增大mid试试，
// 注意dividend和divisor为负值，mid为正值，注意大小关系关系不用弄反了
// 注意 divisor * mid = dividend的情况这里也是增大了mid，后续范围进一步缩小，到left = right时一定可以把商找出来
//false表示表示divisor * mid < dividend,此时应该减少mid试试
boolean b = quickAdd(divisor, mid, dividend);
if (b) {
//这里为什么是b==true才有ans = mid？以及上面为什么left<=right 而非 left < right?确实很难理解
// 7/(-3) 得-2 这里会出现left = right = 3的情况，但2才是正确答案
/**
* 还是以7/(-3)举例
* right会不断缩小，直至有一次循环进来left=1，right=3 => mid = 2
* 算出来divisor * mid >= dividend (-6 >= -7)
* 此时-2已经是正确答案，并且已赋值给ans
*
* 下一轮循环 left = 3 ，right = 3 这里就说明while的条件应该是left <= right而非left < right
* mid = 3.进入b = false的循环
*
* 下一次到while语句时
* right=2 left = 3 循环跳出
*
* 这里还有一个关键，因为b==true表示divisor * mid >= dividend，其中包括了divisor * mid == dividend
* 的情况，如果divisor * mid == dividend，那mid当然是正确答案。
* 如果divisor * mid < dividend，比如-3 * 2 < -7,这里mid也可能是正确答案
* 但如果divisor * mid > dividend，那么mid一定不是正确答案，
* 所以 ans = mid 一定在divisor * mid >= dividend的分支
*/
ans = mid;
if (mid == Integer.MAX_VALUE) {
break;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return rev ? -ans : ans;
}
/**
* 快速乘
* 注意： divisor<0,mid>0,dividend<0 累加的过程是往x轴负方向靠近的过程
* 累加的结果应该比dividend大（绝对值比dividend的小），一旦比dividend小了，说明这个mid肯定偏大了，应返回false
* 同时为了累加结果朝过int的边界，判断条件应注意写法
* 相当于二进制的竖式运算！！
*/
public boolean quickAdd(int divisor, int mid, int dividend) {
int result = 0;
int add = divisor;
while (mid != 0) {
//当前mid最后一位为1
if ((mid & 1) == 1) {
if (result < dividend - add) {
return false;
}
result += add;
}
// 注意，add变为原来的两倍，相当于算数左移一位，也可能超过dividend的界限，甚至超过int的界限
// 我们保证其不超过dividend的界限，当然也就避免了超过int的界限
// 如果add变为原来的两倍后超过了dividend的界限，因为mid != 1,说明高位肯定有至少1个1，那加上后肯定越界了
if (mid != 1) {
if (add < dividend - add) {
return false;
}
//add += add; //这里不能用add = add << 1,因为add是负数，左移会丢失符号位
//上面的说法是错误，实际上并不会
add = add << 1;
}
mid = mid >> 1; // 等价于 mid >>= 1
}
//走到这里，说明最后的result >= dividend，也就是说绝对值比dividend小
return true;
}
}