【题目】

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

If it is overflow, return MAX_INT.

【分析】

不能用乘除和取模，就只能用加减和位运算。

最简单的方法就是不断的减去被除数。这种方法的迭代次数是结果的大小，即比如结果为n，算法复杂度是O(n)。但是这样会超时。

【代码】

/**********************************   日期：2015-01-24*   作者：SJF0115*   题目: 29.Divide Two Integers*   网址：https://oj.leetcode.com/problems/divide-two-integers/*   结果：AC*   来源：Time Limit Exceeded*   博客：**********************************/#include 
    
     using namespace std;class Solution {public:    int divide(int dividend, int divisor) {        // 当dividend=INt_MAX时，-dividend会溢出,用long long        long long a = dividend >= 0 ? dividend : -(long long)dividend;        // divisor=INt_MAX时，-divisor,用long long        long long b = divisor >= 0 ? divisor : -(long long)divisor;        int count = 0;        // 不断减        while(a >= b){            a -= b;            count ++;        }//while        // 正负        int isPositive = (dividend ^ divisor) >> 31;        if(isPositive == 0){            return count;        }//if        else{            return -count;        }//else    }};int main(){    Solution solution;    int dividend = -2147483648;    int divisor = -1;    int result = solution.divide(dividend,divisor);    // 输出    cout<
     
      <
     
    

【分析二】

通过上面超时的例子可以总结出一点东西，做一些优化。

利用位运算每次把被除数翻倍，从而加速。

【代码二】

/**********************************   日期：2015-01-25*   作者：SJF0115*   题目: 29.Divide Two Integers*   网址：https://oj.leetcode.com/problems/divide-two-integers/*   结果：AC*   来源：Time Limit Exceeded*   博客：**********************************/#include 
    
     #include 
     
      using namespace std;class Solution {public:    int divide(int dividend, int divisor) {        // 当dividend=INt_MAX时，-dividend会溢出,用long long        long long a = dividend >= 0 ? dividend : -(long long)dividend;        // 当divisor=INt_MAX时，-divisor会溢出,用long long        long long b = divisor >= 0 ? divisor : -(long long)divisor;        long long result = 0;        // 不断减        while(a >= b){            long long c = b;            for(int i = 0;a >= c;++i,c <<= 1){                a -= c;                result += 1 << i;            }//for        }//while        // 正负        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)){            result = -result;        }//if        // If it is overflow, return MAX_INT.        if (result > INT_MAX || result < INT_MIN){            result = INT_MAX;        }        return static_cast
      
       (result);    }};int main(){    Solution solution;    int dividend = -2147483648;    int divisor = -1;    int result = solution.divide(dividend,divisor);    // 输出    cout<
       
        <
       
      
     
    

2147483648 overflow 所以返回MAX_INT    2147483647