LeetCode/Solutions/0029.DivideTwoIntegers.cpp at main · jawdan-dev/LeetCode · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int divide(int dividend, int divisor) {
        // Speed thingies.
		ios_base::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);

        unsigned int dend = dividend;
        unsigned int div = divisor;

        int sign = 1;
        if (dividend < 0) {
            dend = -(long long)dividend;
            sign = -sign;
        }
        if (divisor < 0) {
            div = -(long long)divisor;
            sign = -sign;
        }

        unsigned int result = unsigned_divide(dend, div);
        if (sign > 0 && result > INT_MAX) result = INT_MAX;

        return sign < 0 ? -result : result;
    }

    unsigned int unsigned_divide(unsigned int dividend, unsigned int divisor) {
        int bitCount = 0;
        for (int i = 0; i < 32; i++)
            if ((dividend >> i) & 0b1)
                bitCount = i + 1;
        unsigned int q = 0, r = 0;
        for (int i = bitCount - 1; i >= 0; i--) {
            r = r << 1;
            r |= ((dividend >> i) & 0b1);
            if (r < divisor) continue;
            r -= divisor;
            q |= (0b1 << i);
        }

        return q;
    }
};