问题

不用乘、除、mod运算符，求x/y的值 (向下取整)。

算法：二分+倍增（快速乘法）

x/y的值一定会落在[0,x]区间内，所以用二分去寻找答案即可。用快速乘法实现乘法（倍增思想）。

注意：
1. 由于乘法的中间结果可能较大，所以要用long / long long来存储
2. 最后结果也有可能溢出(INT_MIN / -1), 需要特判一下
3. 需要处理正负号

时间复杂度

$O(logN)$

代码

class Solution {
public:
    int divide(int dividend, int divisor) {
        long x = dividend, y = divisor;
        bool neg = false;
        if((x < 0 && y > 0) || (x > 0 && y < 0)) neg = true;
        x = abs(x), y = abs(y);
        long l = 0, r = x;
        while(l < r){
            long mid = l + r + 1>> 1;
            if(mul(mid, y) <= x) l = mid;
            else r = mid - 1;
        }
        long ans = neg?-l:l;
        if(ans > INT_MAX || ans < INT_MIN) ans = INT_MAX; // INT_MIN / -1会溢出
        return (int) ans;

    }

    long mul(long a, long k){
        long ans = 0;
        while(k > 0){
            if(k&1) ans += a;
            a += a;
            k >>= 1;
        }
        return ans;
    }
};