Mind palace

some thoughts

0%

29. Divide Two Integers

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

binary search O(log(dividend/divisor)) time
相当于把商转成二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        dd, dr = abs(dividend), abs(divisor)
        res = 0
        while dd >= dr:
            t, cnt = dr, 1
            while dd >= (t << 1):
                t <<= 1
                cnt <<= 1
            dd -= t
            res += cnt
        if (dividend ^ divisor) < 0:
            return -res
        return min(res, (1 << 31) - 1)
        # return [res, (1 << 31) - 1][res > (1 << 31) - 1] # 相当于array[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int divide(int dividend, int divisor) {
        long dd = labs(dividend), dr = labs(divisor), res = 0; // 这里要用labs因为abs(INT_MIN)还是INT_MIN
        while (dd >= dr) {
            long t = dr, cnt = 1;
            while (dd >= (t << 1)) { // 这里是要避免1/1这个case死循环
                t <<= 1;
                cnt <<= 1;
            }
            dd -= t;
            res += cnt;
        }
        if ((dividend ^ divisor) < 0) return -res;
        return min(res, (long)INT_MAX);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool isNeg = (dividend ^ divisor) < 0;
        long dd = abs((long)dividend), dr = abs((long)divisor);
        if (dr == 0) return INT_MAX;
        long res = 0, v = 0, shift = 0;
        bool changed = false;
        do {
            dd -= (v >> 1);
            res += (shift >> 1);
            v = dr;
            shift = 1;
            changed = false;
            while (v <= dd) {
                v <<= 1;
                shift <<= 1;
                changed = true;
            }
        } while (changed);
        if (!isNeg && res >= INT_MAX) return INT_MAX;
        return isNeg ? -res : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool isNeg = (dividend ^ divisor) < 0;
        long dd = abs((long)dividend), dr = abs((long)divisor);
        if (dr == 0) return INT_MAX; // x/0
        long res = 0;
        while (true) {
            long v = dr;
            long shift = 1;
            bool changed = false;
            while (v <= dd) {
                v <<= 1;
                shift <<= 1;
                changed = true;
            }
            if (changed) {
                dd -= (v >> 1);
                res += (shift >> 1);
            }
            else {
                break;
            }
        };
        if (!isNeg && res >= INT_MAX) return INT_MAX; // INT_MIN/-1
        return isNeg ? -res : res;
    }
};