一、 题目
不使用乘法、除法、求余运算实现除法运算,除数和被除数、结果都是用int型。
如果溢出就返回MAX_INT。
二、 分析
看到题目后我立马想到了计算机组成原理中的一位除法和二位除法,不过想想在这里实现起来又是太麻烦了。
那就先试试暴力法吧,被除数 - 除数 = ???一直减减减直到小于等于0,想想自己都觉得超时。。。如下,果然超时
class Solution { public: int divide(int dividend, int divisor) { int count = 0; int flag = 1; if(dividend < 0) flag = -flag; if(divisor < 0) flag = -flag; dividend = abs(dividend); divisor = abs(divisor); while(dividend > 0){ dividend -= divisor; count ++; } return flag * count; } };
那怎么办呢?使用减的思路是对的,但是就看怎样加快步骤了,只有移位了,我们每次如果够减的话就增大移位,直到不够减,此时说明该数够大了,然后当被除数减过这个数了,虽然不能减去除数的大的倍数,但是小的还是可以的,此时我们将n = 0, 再次移位到能减的最大值,当然我们直到这个数一定小于上一个数,依次类推移位依次减少,直到最后被除数小于除数结束。PS:网上很多说将int改为long就不会出现-2147483648的问题,但是我还是遇到了,不知道为什么,就算是他们说的可以AC的代码还是出现了这个问题,我最后特殊处理下这个问题才通过。AC代码如下:
class Solution { public: int divide(int dividend, int divisor) { if(dividend == 0 || divisor == 1) return dividend; int count = 0; int flag = 1; if(dividend < 0) flag = -flag; if(divisor < 0) flag = -flag; long pdividend = abs((long)dividend); long pdivisor = abs((long)divisor); while(pdividend >= pdivisor){ int n = 0; while(pdividend >= pdivisor<<(n + 1)) n++; pdividend -= pdivisor<<n; count += 1<<n; } count = flag * count; if(count <= -2147483648 || count > 2147483647) return 2147483647; return count; } };