原題：29. Divide Two Integers

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

題目大意：不用乘號和除號，取余實(shí)現(xiàn)兩個數(shù)相除

解題思路：

1. 剛開始打算直接不停地減，直到把被除數(shù)減為0止，擔(dān)心當(dāng)數(shù)比較大時可能會超時，但還是打算先試一波：

class Solution {
public:
    int divide(int dividend, int divisor)
    {
        if(divisor==0||(dividend==INT_MIN&&divisor==-1))
            return INT_MAX;
        int sign=((dividend<0)^(divisor>0))?1:-1;
        if(dividend<0)
            dividend=-dividend;
        if(divisor<0)
            divisor=-divisor;
        int ans=0;
        while(dividend-divisor>0)
        {
            dividend-=divisor;
            ans++;
        }
        if(dividend-divisor==0)
            ans++;
        ans*=sign;
        return ans;
    }
};

time_Exceeded.png

2. 對于被除數(shù)a和除數(shù)b，我們可以先a-b,如果大于0，再a-2b,再a-2(2*b),b每次翻倍，當(dāng)不能再減后，a-=b;再從a-b開始
   比如11/3,先10-3，發(fā)現(xiàn)大于0，將3擴(kuò)大2倍為6，再10-6，發(fā)現(xiàn)還是大于0，于是將6擴(kuò)大2倍即12，再11-12，發(fā)現(xiàn)小于0，于是不能再減了，最多可以減到6，即11-6=5，還剩下5，前面翻倍操作進(jìn)行了2次，相當(dāng)于減了4次，每翻一倍，操作2次。于是現(xiàn)在用5-3，發(fā)現(xiàn)大于0，于是將3擴(kuò)大2倍為6,而5-6<0,所以只能減3，這里沒有進(jìn)行翻倍，操作了一次；還剩下5-3=2，小于3，此時已經(jīng)減完了；共減了2+1=3次，即商為3；
3. 特殊情況：除數(shù)為0，返回最大值；當(dāng)被除數(shù)為-2147483648(最小負(fù)數(shù)),除數(shù)為-1，此時商應(yīng)該是2147483648.但int最大值為2147484647，超限，于是返回最大值。

代碼如下：

class Solution {
public:
    int divide(int dividend, int divisor)
    {
        if(divisor==0||(dividend==INT_MIN&&divisor==-1))
            return INT_MAX;
        int sign=(dividend<0)^(divisor>0)?1:-1;
        if(dividend<0)
            dividend=-dividend;
        if(divisor<0)
            divisor=-divisor;
        int dividend_1=dividend,divisor_1=divisor;
        int step=1,ans=0;
        while(dividend_1-divisor>0)
        {
            divisor_1=divisor;
            step=1;
            while(dividend_1-(divisor_1<<1)>0)
            {
                divisor_1<<=1;
                step++;
            }
            dividend_1-=divisor_1;
            ans+=(1<<(step-1));
        }
        if(dividend_1-divisor==0)
            ans++;
        ans*=sign;
        return ans;
    }
};