29-两数相除

LeetCode 29. 两数相除

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

method: 倍增

a整除b，就是看a可以由多少个b累加而成，所以每次让a减去b，看可以减多少次

倍增的思想是，每个只减一个b太少，可以b、2b、4b这样递增，这样由原来的$O(n)$变成$O(logn)$

long div(long a, long b) {
    if (a < b) return 0;
    long tmp = b;
    long cnt = 1;
    while (tmp + tmp <= a) {
        tmp = tmp + tmp;
        cnt = cnt + cnt;
    }
    return cnt + div(a - tmp, b);
}
int divide(int dividend, int divisor) {
    if (divisor == 1) return dividend;
    if (divisor == -1) {
        if (dividend > INT_MIN) return -dividend;
        return INT_MAX; // INT_MIN/-1会溢出，只能取到INT_MAX
    }
    long a = dividend;  // 会溢出，先转成long
    long b = divisor;
    int sign = 1;
    if (a < 0) {
        a = -a; // 转变为正数
        sign = -sign;
    }
    if (b < 0) {
        b = -b; // 转变为正数
        sign = -sign;
    }
    long res = div(a, b);
    if (sign > 0) return res;
    return -res;
}