给定两个整数，被除数 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。
解：
public class Test {
public static void main(String[] args) {
System.out.println(divide(2147483647, 2));
}
// 二分查找：x/y的结果必然在[0,x]区间中
public static int divide(int dividend, int divisor) {
long res = 0;// 用long存储
long x = dividend;// 转成用long存储
long y = divisor;// 转成用long存储
boolean negative = false;
if ((x > 0 && y < 0) || (x < 0 && y > 0))
negative = true;
if (x < 0)
x = -x;// 都搞成正数
if (y < 0)
y = -y;
long left = 0;
long right = x;// left 和 right分别指向[0,x]区间的两端
while (left < right) {// 经典二分法
long mid = (left + right + 1) >> 1;
if (quickMulti(mid, y) <= x) {
left = mid;
} else {
right = mid - 1;
}
}
res = negative ? -left : left;
if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE)
return Integer.MAX_VALUE;
return (int) res;
}
// 快乘法
public static long quickMulti(long a, long b) {
long res = 0;// 用long存
while (b > 0) {
if ((b & 1) == 1) {
res += a;
}
b >>= 1;// 除以2
a += a;// 乘以2，(b/2)*(a*2)结果不变
}
return res;
}
}