問題描述

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

問題本身很簡(jiǎn)單，就是不用乘除法和求余運(yùn)算，完成簡(jiǎn)單的整數(shù)除法。（如果溢出，就返回 INT_MAX就好）。

思路1 - 原始思路

問題看起來很簡(jiǎn)單，我們只需要沿用整數(shù)除法的定義，逐次累加除數(shù)直至其剛好大于或者等于被除數(shù) - 除數(shù)，結(jié)果就一目了然了。
當(dāng)然這里說的是除數(shù)和被除數(shù)都是正整數(shù)的情況，那么當(dāng)有一方或者兩方為負(fù)數(shù)的時(shí)候，問題就不能簡(jiǎn)單這么解決了，不過也只需要存儲(chǔ)一個(gè)兩個(gè)運(yùn)算成員符號(hào)的異或結(jié)果sign，最后輸出的時(shí)候 return sign ? result : -result 這樣也就解決了。

上面說的思路，簡(jiǎn)單累加的話，就是一個(gè)O(N)的平均復(fù)雜度，對(duì)于某些問題來說，O(N)的復(fù)雜度完全是可以接受的，然而對(duì)于一個(gè)本來只需要一條 CPU 指令就可以搞定的問題來說，做成這個(gè)復(fù)雜度也實(shí)在是令人惱火。

不過還是先把代碼寫出來吧，看看能不能AC：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;
        if(!dividend)
            return 0;
        int result = 0, sum = 0;
        bool sign = bool(dividend < 0) == bool(divisor < 0);
        unsigned long long dividendabs = labs(dividend);
        unsigned long long divisorabs = labs(divisor);
        while(1) {
            sum += divisorabs;
            result ++;
            if(sum == dividendabs)
                break;
            else if(sum > dividendabs) {
                result --;
                break;
            }
        }
        return sign ? result : -result;
    }
};

果然毫無意外的 TLE了（Time Limit Exceeded）。TLE的測(cè)試?yán)?code>-2147483648，1。誠(chéng)然這個(gè)問題完全可以在入口值判斷那里解決，然而如果測(cè)試?yán)?code>2147483646，1 呢？估計(jì)也會(huì)超時(shí)吧。所以問題還是要從時(shí)間復(fù)雜度這個(gè)問題上解決。

思路2-跑快一點(diǎn)

直觀地分析這個(gè)問題，看起來問題主要還是出在向結(jié)果靠近的速度太慢，如果我們不是線性地累加呢？如果我們每次都翻倍……？根據(jù)經(jīng)驗(yàn)，一旦用這種方式接近，往往可以讓問題降低到 O(logn) 的程度。
讓我們換個(gè)思路，每個(gè)整數(shù)都能轉(zhuǎn)化成若干個(gè)2的n次方之和，這種數(shù)則一共是log2(N)個(gè)，若是從最低位找起，則平均每次運(yùn)行l(wèi)og2(N)/2次，就可以啦。
根據(jù) divisor = dividend * result = dividend * (這些數(shù)之和)，問題就可以解決啦~！而復(fù)雜度則正好是O(log(N) * log(N))。
下面上代碼：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor || (dividend == INT_MIN && divisor == -1) || (dividend == INT_MAX && divisor == 1))
            return INT_MAX;
        if(!dividend)
            return 0;
        int result = 0, sum = 0;
        bool sign = bool(dividend < 0) == bool(divisor < 0);
        long long dividendabs = labs(dividend);
        long long divisorabs = labs(divisor);
        while(divisorabs <= dividendabs) {
            long long temp = divisorabs, doubles = 1;
            while((temp << 1) <= dividendabs) {
                temp <<= 1;
                doubles <<= 1;
            }
            dividendabs -= temp;
            result += doubles;
        }
        return sign ? result : -result;
    }
};

最后AC了，結(jié)果嘛，還不錯(cuò)（逃