runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: number, bit manipulation

Divide Two Integers

📖 description

給定兩個數字 dividend 、 divisor ，回傳 dividend/divisor ，要求不能使用乘除運算以及 mod 運算。

🧠 solution

使用 long 型別避免運算出現溢位，然後使用 bit operation 與加減法來模擬除法。

ex.
    17/3 

    1. (17 >> 2) > 3   (17 >> 2) 等價於 (17/4)
       (17 - (3 << 2) ) = 5
        那此時商就是 4 ，餘數為 5 

    2. (5 >> 1) < 3

    3. (5 >> 0) < 3    (5 >> 0)  等價於 (5/1)
       (5 - (3 << 0)) = 2
       商為 4+1 ，餘數為 2
    

    所以答案為 5

⏳ time complexity

從第 32 個 bit 一路往下，時間複雜度為 O(log(n))
總時間複雜度 O(log(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {  // 邊緣測資
            return INT_MAX;
        }
        bool flag = (dividend>0 == divisor>0);       // 答案的正負號 
        long a = labs(dividend), b = labs(divisor);  // 避免溢位
        long ans = 0;
        for(int x=32;x>=0;x--){
            if((a>>x)>=b){
                ans += 1<<x;    // 商
                a -= b<<x;      // 餘
            }
        }
        if(flag){
            return ans;
        }
        else{
            return -ans;
        }
    }
};