Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
in.txt
solve.c

README.md

Divide Two Integers

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

If it is overflow, return MAX_INT.

Solution

不能用/ * % 做除法运算,于是自然想到使用减法.

但是减法运算太慢了,每次只能减一个除数.

比如100 / 25 = 100 - 25 - 25 - 25 - 25,于是100 / 25 = 4.

很显然100能够直接减去25 * 4 == 100, 而不能使用*,但可以想到使用左移运算符达到效果.

于是我们尽可能每次减得更大,而减数必须是除数的2的幂倍数,比如125 / 5, 5的2次幂倍数关系为5 10 20 40 80 160. 则125 = 125 - 80 - 40 - 5.

于是每次可以遍历能够减去的最大数,直到被减数小于减数。

为了处理负数问题,我们可以先判断出符号,然后取绝对值,当做正数处理.

但有一种情况需要格外处理, 即INT_MIN,如果取绝对值,就会溢出,这种情况使用int没法解决,比如INT_MIN / -2 . 为了处理这种情况,需要把int类型转化为long,即可避免这种情况.

Code

int getSign(long a, long b)
{
	if ((a < 0 && b > 0) || (a > 0 && b < 0))
		return 1;
	return 0;
}
long labs(long a)
{
	return a >= 0 ? a : -a;
}
int divide(int dividend, int divisor)
{
	if (divisor == 0) {  // 除数为0
		return dividend >= 0 ? INT_MAX : INT_MIN;
	}
	long n = dividend; // 防止溢出,当其中一个=INT_MIN
	long m = divisor;
	int sign = getSign(n, m); // 保存结果的符号
	n = labs(n);
	m = labs(m);
	long ans = 0;
	long a; // 防止 a << 1溢出
	long k;
	while (n >= m) {
		a = m, k = 1;
		while (n > (a << 1)) {
			a <<= 1;
			k <<= 1;
		}
		n -= a;
		ans += k;
	}
	ans = sign ? -ans : ans;
	if (ans > INT_MAX)
		return INT_MAX;
	if (ans < INT_MIN)
		return INT_MIN;
	return ans;
}
You can’t perform that action at this time.