29. Divide Two Integers (INT; Overflow, Bit)

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

If it is overflow, return MAX_INT.

思路I：做减法，直到被除数<除数。但结果 Time Limit Exceeded

class Solution {

public:

  int divide(int dividend, int divisor) {

    if(divisor==) //分母为0

        return INT_MAX;

    long int lDividend = dividend;

    long int lDivisor = divisor;

    long int quote=;

    bool pos = (lDividend>= && lDivisor>) || (lDividend< && lDivisor<);

    lDividend = abs(lDividend);

    lDivisor = abs(lDivisor);

    while(lDividend >= lDivisor){

        lDividend-=lDivisor;

        quote++;

    }

    if(pos && -quote==INT_MIN){

        return INT_MAX;

    }

    return (int) pos?quote:(-quote);

  }

};

思路II：任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=2^0+2^1+2^2+...+2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基，移动k位。接下来我们每次尝试减去这个基，如果可以则结果增加加2^k。然后基继续右移迭代，直到基<divisor为止。因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(logn)。

class Solution {

public:

  int divide(int dividend, int divisor) {

    if(divisor==) //分母为0

        return INT_MAX;

    int res = ;

    if(dividend==INT_MIN) //handle overflow

    {

        if(divisor==-)

            return INT_MAX;

        res = ;

        dividend += abs(divisor);

    }

    if(divisor==INT_MIN) //handle overflow

        return res;

    bool isNeg = ((dividend^divisor)>>!=)?true:false; //判断两数相乘除的结果

    dividend = abs(dividend);

    divisor = abs(divisor);

    int digit = ; //标记除数乘了多少次2

    //将除数向左移到最大

    while(divisor<=(dividend>>)) //与被除数除2相比，为防止overflow

    {

        divisor <<= ;

        digit++;

    }

    while(digit>=)

    {

        if(dividend>=divisor)

        {

            dividend -= divisor;

            res += <<digit; //除数左移了digit次，商就要加上2^digit

        }

        divisor >>= ;

        digit--;

    }

    return isNeg?-res:res;

  }

};

巴特西

29. Divide Two Integers (INT; Overflow, Bit)

最新文章

热门文章