题目链接:Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
这道题的要求是在不使用乘法、除法、取模运算的前提下实现两个整数相除。如果溢出,返回MAX_INT。
这道题的直接思路是用被除数不断减去除数,直到为0。这种方法的迭代次数是结果的大小,即比如结果为n,算法复杂度是O(n)。
可以采用位运算进行优化,即模拟计算机上的除法运算。将整数转化成二进制形式,即num = a0*2^0 + a1*2^1 + a2*2^2 + … + an*2^n。基于以上这个公式以及左移一位相当于乘以2,可以先让除数左移直到大于被除数之前得到一个最大的基数。然后每次用被除数去减去这个基数,同时结果增加2^k。接下来继续重新左移除数左移迭代,直到被除数不大于除数为止。因为这个方法的迭代次数是按2的幂直到结束,所以时间复杂度为O(logn)。
值得注意的地方,主要就是处理符号和溢出问题。对于溢出问题,可以先采用long long进行计算,也可以在移位前判断移位后是否溢出。
时间复杂度:O(logn)
空间复杂度:O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
int divide(int dividend, int divisor)
{
int sign = (dividend < 0) ^ (divisor < 0) ? - 1 : 1;
long long res = 0, m = abs((long long)dividend), n = abs((long long)divisor);
while(m >= n)
{
long long t = n, i = 1;
while(t << 1 < m)
{
t <<= 1;
i <<= 1;
}
m -= t;
res += i;
}
if(sign < 0)
res = -res;
return res > INT_MAX ? INT_MAX : res;
}
};