Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

 

思路：实现两个整数的除法，不能使用乘法，除法和移位操作。首先想到的是减法，但是减法速度太慢，比如10000000/1，总共需要10000000次减法，所以不适用。

因不能使用乘法，可以使用移位操作来代替乘法。本质上就是：(x+y)/m = x/m + y/m。m左移一位，就相当于乘以了2，依次类推。

代码如下：

 

int divide(int dividend, int divisor) {    unsigned res = 0;        if(divisor == 0)    return 0x7fffffff;        unsigned int posdividend = (dividend < 0)?-dividend:dividend;    unsigned int posdivisor = (divisor < 0)?-divisor:divisor;        while(posdividend >= posdivisor)    {    	int n = 0;    	unsigned int tmp = posdivisor;    	while(tmp <= posdividend)    	{    		tmp <<= 1;    		n++;    		if(tmp == 0)break;    	}	    	res += 1 << (n-1);		if(tmp == 0)	posdividend -= 0x80000000;		else    	posdividend -= tmp>>1;    	    }    if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))        return -res;    if(res == 0x80000000)   return 0x7fffffff;    return res;    }