题目

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

分析

对两个整数进行除运算，但不能使用乘、除、模运算符。如果结果溢出，返回INT的最大值。
如果使用加减运算符，运算速度会很慢。还有一个移位运算符，直接扩大2倍。因此可以借助下面的思想：

32/3=(3*2*2*2+3*2+2)/3=2*2*2+2+1

因此逐渐使用除数乘以2的几次幂减少被除数，最后把过程中的相加即是结果。

int divide(int dividend, int divisor) {
    if((divisor==0)||(dividend==-2147483648&&divisor==-1))return INT_MAX;
    else
    {
        long long ans=0,positive=0,a=0,b=0,p1=dividend,p2=divisor;
        if((dividend>0&&divisor>0)||(dividend<0&&divisor<0))positive=1;
        if(p1<0)p1=-p1;
        if(p2<0)p2=-p2;
        while(p1>=p2)
        {
            a=p2;
            b=1;
            while(a<=p1/2)
            {
                a=a<<1;
                b=b<<1;
            }
            p1=p1-a;
            ans=ans+b;
            //printf("%d %d %d\n",p1,p2,ans);
        }
        if(positive==1)
            return ans;
        else return -ans;
    }
}