29. 两数相除

题目链接

二分+倍增

• 不使用除法算除法，很自然就想到二分答案

  • 但是需要注意，要找到比商小，但是离商最接近的整数，所以二分的时候，需要l=mid，循环条件为l<r

• 但是也不能使用乘法，所以需要用倍增，原理如下

  • 假设a与b相乘，即为a个b相加
  • 我们将a用二进制表示，a & (1 << x)为1，即代表有2^x个b相加
  • 将式子转换为(a >> x) & 1和(b << x)，那么就只需在迭代时右移a和左移b即可

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0)
            return 0;
        if(dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        int signal = (dividend ^ divisor) < 0 ? -1 : 1;
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        long l = 0, r = a;
        while(l < r){
            long mid = (l + r + 1) >> 1;
            long c = mul(mid, b);
            if(c < a) l = mid;
            else if(c > a) r = mid - 1;
            else return signal * (int) mid;
        }
        return signal * (int) l;
    }
    private long mul(long a, long b){
        long ans = 0;
        while(a > 0){
            if((a & 1) == 1)
                ans += b;
            a >>= 1;
            b <<= 1;
        }
        return ans;
    }
}

• 二分的时间复杂度是O(logn)，倍增乘法的时间复杂度也是O(logn)，所以最终的时间复杂度是O(log²n)

二进制枚举

• 要避免乘除法，核心思想一定是用位运算来代替乘2和除2，但是用倍增来代替乘法，显然是过于复杂了，为何不直接用位运算来计算商呢？
• 眼界放开，就直接枚举商的二进制的每一位，这样枚举的结果都是2的幂，乘法可以用(b << i)来表示，省去了倍增这一步骤，枚举二进制的时间复杂度也和二分查找相同
• 本质上来说，就是贪心，先用大数去乘，再用小数去乘，所得结果相加即为最终答案

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0)
            return 0;
        if(dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        int signal = (dividend ^ divisor) < 0 ? -1 : 1;
        int ans = 0;
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        for(int i = 32; i >=0; i--)
            if((a >> i) >= b){
                ans += (1 << i);
                a -= (b << i);
            }
        return signal * ans;
    }
}