# 29 - Divide Two Integers

解法一 - Dividend - divisor

這題一開始會想要把 search space 當成 divisor - dividend 之間，然後每次變一半，但如果要判斷要捨棄哪一半的 search space，就會變得有點尷尬，因為要看 divisor*mid 是否大於 dividend。

換個角度想，其實要算出答案就是要知道 dividend 可以減掉 divisor 幾次，比如說以 10/3 的例子，10 可以減掉 3 個 3。但如果只是一個 divisor 一個 divisor 慢慢減，就得減 dividend/divisor 次。

最直觀的實作法大概長得像下面這樣：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;
        if(divisor == 1) return dividend;

        long res=0;

        int d;
        bool minFlag = false;
        if(dividend == INT_MIN) {
            d = INT_MAX;    
            minFlag = true;
        }
        else
            d = abs(dividend);

        int n = abs(divisor);

        while(d>=n) {
            if(minFlag && res>0) {
                d++;
                minFlag = false;
            }
            d -= n;
            res++;
        }

        return (dividend > 0) == (divisor > 0) ? res : -res;
    }
};

裡面已經包含了幾個小 trick，例如：

1. 處理了 INT_MIN/-1 這種會 overflow 的 corner case：

   if(dividend == INT_MIN && divisor == -1) return INT_MAX;

2. dividend 如果是 INT_MIN，那不能直接取 abs，因為會 overflow

不過這樣一個個減太慢，會在某些 case 上 TLE，例如

2147483647
3

解法二 - Bit Manipulation 二分

這題可以用 iterative/recursive 的方式來寫，主要精神就是要盡量一次減掉多一點 divisor，就可以不需要慢慢減：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        if (divisor == 1) return dividend;

        int res = 0;

        long a = abs((long)dividend);
        long b = abs((long)divisor);
        while(a >= b) {
            int shift = 0;
            while(a >= (b << shift))
                shift++;
            a -= (b << (shift-1));
            res += (1 << (shift-1));
        }

        return (dividend>0) == (divisor>0) ? res : -res;
    }
};