https://leetcode-cn.com/problems/divide-two-integers/
用最简单的算法——直接一个一个去减，结果是不出意外的超时了。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func divide(dividend int, divisor int) int {
var isPositive bool=true
if dividend<0{
dividend=-dividend
isPositive=!isPositive
}
if divisor<0{
divisor=-divisor
isPositive=!isPositive
}
var output int32=0
const INT_MAX = int32(^uint32(0) >> 1)
for dividend>=divisor{
if isPositive{
if output>INT_MAX-1{
break
}
}else{
if output<^INT_MAX+1{
break
}
}
dividend-=divisor
output++
}
if isPositive{
return int(output)
}else{
return int(-output)
}
}
|
改进了一下算法，增加了一个类似 TCP 的慢启动过程，让速度快了很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| func divide(dividend int, divisor int) int {
var isPositive bool=true
if dividend<0{
dividend=-dividend
isPositive=!isPositive
}
if divisor<0{
divisor=-divisor
isPositive=!isPositive
}
if dividend<divisor{
return 0
}
var output int32=0
const INT_MAX = int32(^uint32(0) >> 1)
for dividend>=divisor{
if isPositive{
if output>INT_MAX-1{
break
}
}else{
if output<^INT_MAX+1{
break
}
}
var pow int32=1
myDivisor:=divisor
for t:=dividend-myDivisor;t>=0;t=dividend-myDivisor{
dividend=t
output+=pow
myDivisor+=myDivisor
pow+=pow
}
}
if isPositive{
return int(output)
}else{
return int(-output)
}
}
|
还可以把加法改成移位，参考了一个 Discuss 中的描述。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| func divide(dividend int, divisor int) int {
var isPositive bool=true
if dividend<0{
dividend=-dividend
isPositive=!isPositive
}
if divisor<0{
divisor=-divisor
isPositive=!isPositive
}
if dividend<divisor{
return 0
}
var output int32=0
const INT_MAX = int32(^uint32(0) >> 1)
for dividend>=divisor{
if isPositive{
if output>INT_MAX-1{
break
}
}else{
if output<^INT_MAX+1{
break
}
}
var pow int32=1
myDivisor:=divisor
for t:=dividend-myDivisor;t>=0;t=dividend-myDivisor{
dividend=t
output+=pow
myDivisor<<=1
pow<<=1
}
}
if isPositive{
return int(output)
}else{
return int(-output)
}
}
|
还有一种比较顺畅的思路是将除数先不断左移，直到刚好比被除数小，然后做一次减法，接着就是将除数不断右移，一旦比除数小，就再用被除数减去除数，直到除数右移为0，运算结束。可以参考这里https://leetcode-cn.com/problems/divide-two-integers/solution/xiao-xue-sheng-du-hui-de-lie-shu-shi-suan-chu-fa-b/