首页 > 代码库 > 29. Divide Two Integers

29. Divide Two Integers

2024-09-03 00:50:40   220人阅读

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

If it is overflow, return MAX_INT.

分析

不能用除法，所以使用减法不断减 除数，同时对 除数 倍乘，进行加速
除数：3 -> 6 -> 12 ...

边界条件：
1 除数为0，溢出
2 被除数 INT_MIN，同时除数 -1，溢出，因为labs(MIN_INT) = INT_MAX + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int divide(int dividend, int divisor) {
        if( !divisor || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;
        int sign = (dividend<0) ^ (divisor<0)? -1: 1;
        long long a = labs(dividend);
        long long b = labs(divisor);
        long long result = 0;
        while( a >= b){
            for(long long i = 1, d = b; a >= d; ++i, d <<= 1){
                a -= d;
                result += 1 << (i-1);
            }
        }
        return result*sign;
    }
};




null


29. Divide Two Integers


联系
我们