29. Divide Two Integers

题目:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3

Example 2:
Input: dividend = 7, divisor = -3
Output: -2

不用乘法、除法和取模，求两个int的比值。

思路1：（超时）

简单的转换成减法，结果超时了。

int divide(long dividend, long divisor) {//超时
	int res = 0, flag = 1;
	if (dividend < 0)
		flag *= -1;
	if (divisor < 0)
		flag *= -1;
	if (divisor == 1)
		return dividend;
	if (divisor == -1) 
		if (dividend == INT32_MIN)
			return INT32_MAX;
		else
			return -dividend;
	while (abs(dividend) >= abs(divisor)) {
		dividend -= divisor*flag;
		++res;
		if (res > INT32_MAX || res < INT32_MIN)
			return INT32_MAX;
	}
	return res*flag;
}

思路2：

同样是转换成减法，但进行优化，将简单的每次减去减数，变成依次减去减数的整数倍。

int divide(long dividend, long divisor) {
	if (dividend == INT_MIN && divisor == -1) return INT_MAX;
	long a = abs(dividend), b = abs(divisor), c;
	long res = 0;
	while (a >= b) {
		c = b;
		for (int i = 0; c <= a; ++i) {
			a -= c;
			c = c << 1;
			res += 1 << i;
		}
	}
	return ((dividend^divisor) >> 31) ? (int)(-res) : (int)res;
}