首页 > 代码库 > 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; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。