LeetCode/DivideTwoIntegers.cpp at master · Riddance/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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Solution {
public:
    int divide(int dividend, int divisor) {
        long long int quotient = 0;
        long long int sign = 0;

        long long int dividend_ = dividend;
        long long int divisor_ = divisor;

        if (dividend_ > 0 && divisor_ > 0)
            sign = 0;
        else if (dividend_ < 0 && divisor_ < 0)
        {
            sign = 0;
            dividend_ = -dividend_;
            divisor_ = -divisor_;
        }
        else if (dividend_ > 0 && divisor_ < 0)
        {
            sign = 1;
            divisor_ = -divisor_;
        }
        else if (dividend_ < 0 && divisor_ > 0)
        {
            sign = 1;
            dividend_ = -dividend_;
        }
        else
            return 0;

        long long int key = divisor_;
        long long int value = 1;

        while (dividend_ >= key)
        {
            dividend_ = dividend_ - key;
            key = key << 1;

            quotient = quotient + value;
            value = value << 1;
        }

        while (dividend_ >= divisor_)
        {
            if (dividend_ < key && key > divisor_)
            {
                key = key >> 1;
                value = value >> 1;
                continue;
            }

            dividend_ = dividend_ - key;
            quotient = quotient + value;
        }

        if (sign)
            return -quotient;
        else
            return quotient;
    }
};

class Solution {
public:
    int divide(int dividend, int divisor) {
        int sign = 1;

        int result = 0;

        long long int lhs = dividend;
        long long int rhs = divisor;
        if (lhs < 0) {
            lhs = -lhs;
            sign = -sign;
        }

        if (rhs < 0) {
            rhs = -rhs;
            sign = -sign;
        }

        long long int key = rhs;
        long long int val = 1;

        while (lhs >= rhs) {
            if (key < rhs) {
                break;
            }

            if (key <= lhs) {
                lhs = lhs - key;
                result = result + (int)val;
            }

            if (key < lhs) {
                key = key << 1;
                val = val << 1;
            }

            if (key > lhs) {
                key = key >> 1;
                val = val >> 1;
            }
        }

        return sign < 0 ? -result : result;
    }
};