LeetCode #29 – Divide Two Integers [思路]

Link

点击打开题目链接

Problem

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

If it is overflow, return MAX_INT.

Mean

计算INT内的两个数相除,不能使用乘法、除法和取模。

Analysis

首先想到除法变成减法,但是减法太慢了。这样就从b开始一直减,b每次变为原来的两倍。直到减没。注意判断溢出的情况。

Code

class Solution {
public:
    using ll = long long;
    int divide(int dividend, int divisor) {
        int flag = (dividend >> 31) - (divisor >> 31);
        ll a = abs((ll)dividend), b = abs((ll)divisor), ans = 0;
        while(a >= b) {
            ll cur = b;
            for (int i = 0; a >= cur; ++i) {
                a -= cur;
                ans += 1 << i;
                cur <<= 1;
            }
        }
        if(flag) ans = -ans;
        if(ans > INT_MAX || ans < INT_MIN)
            return INT_MAX;
        return static_cast<int>(ans);
    }
};

欢迎留言