两数相除
大家儿童节快乐，今天是一道二分查找标签下通过率最低的一题，来自leetcode，难度为中等，但是Acceptance很低，仅为19.6%（截止2020.6.1）。我们来看下该题到底难在哪。
题目如下
两数相除
给定两个整数，被除数 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提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
回复0000查看更多题目
解题思路
该题的难度就在于不能使用乘除法，但是没有限制不能使用加减法和位运算，所以怎么用这些数学计算方法逼近除法结果是关键。
最直接的思路，用被除数不断地减去除数，直到小于0。但是这种方法效率太低，不满足时间要求。
该题既然在leetcode上被打上了二分查找的标签，考虑采用二分查找的思路结题。
设被除数为a, 除数为b；
if(abs(dividend) < abs(divisor))， 那么返回0。
否则，初始化结果ans=1，如果b + b <= a, 则尝试将b加倍，即b = b + b，结果也加倍ans = ans + ans，直到b + b > a；
此时令被除数a = a - b，相当于a减去了2^ans个b。
重复上面的步骤，直到a<b，此时ans=0；最后将每一步得到的ans相加。
仔细思考就发现是其实是用 K = b0 * 2^0 + b1 * 2^1 + b2 * 2^2 + ... + bn * 2^n + ... 去逼近真实值。
当然在实际编码过程中还有注意边界和数值问题, 包括：
- 正负号
- 溢出 if(abs(dividend) < abs(divisor))， 那么返回0
这也是该题通过率低的原因之一。思路有了，代码如下：
代码如下
C++版
public int divide(int dividend, int divisor) { // 被除数 除数
if(divisor == -1 && dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE; // 溢出
int sign = 1;
if((dividend > 0 && divisor < 0)||(dividend < 0 && divisor > 0))
sign = -1;
if(divisor == 1) return dividend;
if(divisor == -1) return -dividend;
int a = dividend>0 ? -dividend : dividend;
int b = divisor>0 ? -divisor : divisor;
// 都改为负号是因为int 的范围是[2^32, 2^32-1]，如果a是-2^32，转为正数时将会溢出
if(a > b) return 0;
int ans = div(a,b);
return sign == -1 ? -ans : ans;
}
int div(int a, int b)
{
if(a > b) return 0;
int count = 1;
int tb = b;
while(tb+tb >= a && tb+tb < 0){ // 溢出之后不再小于0
tb += tb;
count += count;
//System.out.println(tb + " " + count + " " + count*b);
}
return count+div(a-tb,b);
}
