29. Divide Two Integers.md

29. Divide Two Integers

Problem

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

tag:

Solution

减法模拟除法

• 直接相减 被除数循环减去除数，统计被除数包含的除数个数，时间复杂度O(n)

• 二分搜索加速 上述方法每次减去一个除数，我们可以提高通过放大除数倍数加快运算速度 例如除数不断乘2（左移一位），直到大于被除数；然后被除数减去该数，继续上述循环 算法时间复杂度log(n)

• 溢出情况

被除数等于0 被除数等于MIN_INT，除数等于-1

java

    public int divide(int dividend, int divisor) {
        if( divisor==0 || (dividend==Integer.MIN_VALUE&&divisor==-1) ) return Integer.MAX_VALUE;
        long dvd = Math.abs((long)dividend), dvs = Math.abs((long)divisor);
        int res = 0;
        while(dvd >= dvs) {
            long i=1, tmp = dvs;
            while(dvd > (tmp<<1)) {
                tmp <<= 1;
                i <<= 1;
            }
            res += i;
            dvd -= tmp;
        }
        return (dividend<0) ^ (divisor<0) ? -res : res;
    }

go