leetcode:Divide Two Integers

一、 题目

不使用乘法、除法、求余运算实现除法运算，除数和被除数、结果都是用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;
}
};

最后

以上就是搞怪金鱼为你收集整理的leetcode:Divide Two Integers的全部内容，希望文章能够帮你解决leetcode:Divide Two Integers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。