[LeetCode]29.Divide Two Integers

【题目】

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 <iostream>
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<<result<<endl;
    return 0;
}

【分析二】

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

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

【代码二】

/*********************************
*   日期：2015-01-25
*   作者：SJF0115
*   题目: 29.Divide Two Integers
*   网址：https://oj.leetcode.com/problems/divide-two-integers/
*   结果：AC
*   来源：Time Limit Exceeded
*   博客：
**********************************/
#include <iostream>
#include <climits>
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<int>(result);
    }
};

int main(){
    Solution solution;
    int dividend = -2147483648;
    int divisor = -1;
    int result = solution.divide(dividend,divisor);
    // 输出
    cout<<result<<endl;
    return 0;
}

之前忽略一个细节：If it is overflow, return MAX_INT.

2147483648 overflow 所以返回MAX_INT    2147483647