Divide two integers without using multiplication, division and mod operator.
最直观的方法是，用被除数逐个的减去除数，直到被除数小于0。这样做会超时。 本文地址
那么如果每次不仅仅减去1个除数，计算速度就会增加，但是题目不能使用乘法，因此不能减去k*除数，我们可以对除数进行左移位操作，这样每次相当于减去2^k个除数，如何确定k呢，只要使 (2^k)*除数 <= 当前被除数 <(2^(k+1))*除数.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class
Solution {
public
:
int
divide(
int
dividend,
int
divisor) {
unsigned
int
divd = dividend, divs = divisor;
//使用unsigned防止-2147483648符号取反后溢出
if
(divisor < 0)divs = -divs;
//负数全部转化为正数
if
(dividend < 0)divd = -divd;
int
res = 0;
while
(divd >= divs)
{
long
long
a = divs;
//使用long long防止移位溢出
int
i;
for
(i = 1; a <= divd; i++)
a <<= 1;
res += (1 << (i-2));
divd -= (divs << (i-2));
}
return
(dividend>0 ^ divisor>0) ? -res : res;
}
};
|
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3795342.html，如需转载请自行联系原作者
