LeetCode 29. Divide Two Integers

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

思路

边界条件：比如被除数、除数是0，另外结果的正负号要注意。
除法可以用减法实现，不过如果干减的话会很费时间，所以要想想怎么加速。
容易知道，一个数左移一位相当于乘以2。我们可以一次次把除数乘以2试探一下，到底最多能减掉 2^n*除数 多少次，这就相当于做了2^n次除法。由于试探的时候一次次做了乘方，所以试探的次数是log级别的，比原来一个个减要快多了。

代码

class Solution {
public:
	int divide(int dividend, int divisor) {
		if (dividend == 0)
			return 0;
		if (divisor == 0)
			return INT_MAX;
		bool posResult = true;
		if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor >0))
			posResult = false;
		long long lDividend = dividend;
		if (lDividend < 0)
			lDividend = ~(lDividend-1);
		long long lDivisor = divisor;
		if (lDivisor < 0)
			lDivisor = ~(lDivisor-1);
		long long currDivisor = lDivisor;
		long long accRate = 1;
		long long result = 0;
		while (lDividend >= lDivisor) {
			while ((currDivisor << 1) < lDividend) {
				currDivisor <<= 1;
				accRate <<= 1;
			}
			while (currDivisor > lDividend) {
				currDivisor >>= 1;
				accRate >>= 1;
			}
			lDividend -= currDivisor;
			result += accRate;
		}
		if (posResult) {
			if (result > INT_MAX) {
				return INT_MAX;
			}
			else {
				return (int)result;
			}
		}
		else {
			result = -result;
			if (result < INT_MIN)
				return INT_MIN;
			else
				return (int)result;
		}
	}
};