首页 > 代码库 > leetcode——Divide Two Integers 不用乘除取余操作求除法(AC)

leetcode——Divide Two Integers 不用乘除取余操作求除法(AC)

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

题目只有简单的一句话,看起来可真简单啊,呵呵,假象。这个题目的难点在于对时间效率的限制和边界值的测试。第一印象肯定是循环一个个把因子从被除数中减去不久行了么,可是对于比如INT_MAX/1或者INT_MIN/1之类的执行时间长的可怕,会超出时间限制。改善时间效率的思路是参考网上别人代码,将因子不断乘以2(可以通过移位实现,同时结果也从1开始不断移位加倍),然后和被除数比较,等到大于被除数一半了,就从被除数中减去,将因子个数叠加入结果中。然后在剩下的被除数中采用同样的方法减去小于其一半的因子和,循环往复。我在代码中使用了unsigned int类型存储因子和,于是存在这种情况INT_MIN/INT_MIN,这样如果在循环条件判定是加上等于的情况,因子和移位时可能发生越界,所以等于情况单独考虑了。code如下:

class Solution {
public:
    int divide(int dividend, int divisor) {
        assert(divisor != 0);
        int count = 0, result = 0;
        bool isNeg = false;
        if((dividend<0 && divisor>0)||(dividend>0 && divisor<0))
            isNeg = true;
        unsigned int tDividend = abs(dividend);
        unsigned int tDivisor = abs(divisor);
        unsigned int sum = 0;
        while(tDivisor < tDividend)
        {
            count = 1;
            sum = tDivisor;
            while((sum<<=1) < tDividend)
            {
                count<<=1;
            }
            tDividend -= (sum>>=1);
			result += count;
        }
        if(tDivisor == tDividend)
            result++;
        return isNeg ? (0-result) : result;
    }
};