1、前言

2、思路

假如 a/b，求一个商最简单的方法是，在[0, a) 范围内不断的二分，然后用二分位置的数 mid * b，如果 mid * b 最接近 a，那么乘积就是他们的商。
而题目要求不能用乘法，所以模拟了一个位数乘法，实现原理是：6 * 7 = 6 * (4 + 2 + 1)，(4 + 2 + 1)是7二进制上的1.

3、代码

class Solution {
    public int divide(int a, int b) {
        long x = a, y = b;
        boolean isNeg = false;
        if ((x > 0 && y < 0) || (x < 0 && y > 0)) isNeg = true;
        if (x < 0) x = -x;
        if (y < 0) y = -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 = isNeg ? -l : l;
        if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE;
        return (int)ans;
    }

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