29.Divide Two Integers

這題首先我們先撇除邊界問題, 邊界就是要先處理掉

我們看核心

假設15 / 4= 3 … 2, 自從國小畢業就沒再用過"…" 餘數了

我們一般的做法, 就是15–4–4–4(減了三次),

這題其實也可以, 但這樣減速度會太慢, 我們有沒有辦法加快呢

有的, 我們一開始先用兩倍一直把除數乘大(B), 直到大於被除數

然後我們紀錄總共增加了多少倍, 統一加到商的值, 最後在把原本的被除數剪掉這個乘大的除數(B)

反覆操作值到被除數 小於除數

class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if (divisor == 1 && dividend == INT_MIN)
        {
            return INT_MIN;
        }
        if (divisor == -1 && dividend == INT_MIN)
        {
            return INT_MAX;
        }
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
        long m = labs(dividend);
        long n = labs(divisor);
        int res = 0;
        while (m >= n)
        {
            long t = n;
            long p = 1;
            while (m >= (t << 1))
            {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        return sign == 1 ? res : -res;
    }
};