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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| // @Title: 两数相除 (Divide Two Integers)
// @Author: 15816537946@163.com
// @Date: 2021-10-12 15:35:15
// @Runtime: 4 ms
// @Memory: 2.4 MB
import "math"
func divide(dividend int, divisor int) int {
IntMin := math.MinInt32
IntMax := math.MaxInt32
// 考虑被除数是最小值的情况
if dividend == IntMin {
if divisor == 1 {
return IntMin
}
if divisor == -1 {
return IntMax
}
}
// 考虑除数为最小的情况
if divisor == IntMin {
if dividend == IntMin {
return 1
}
return 0
}
// 考虑被除数为0的情况
if dividend == 0 {
return 0
}
// 一般情况,使用二分查找
// 将所有正数取相反数,这样只需要考虑一种情况
var rev bool
if dividend > 0 {
dividend = -dividend
rev = !rev
}
if divisor > 0 {
divisor = -divisor
rev = !rev
}
// 快速乘
quickAdd := func(y, z, x int) bool {
// x 和 y 是负数, z 是正数
// 需要判断 z * y >= x 是否成立
result, add := 0, y
for z != 0 {
if z&1 == 1 {
// 需要保证 result + add >= x
if result < x-add {
return false
}
result += add
}
if z != 1 {
// 需要保证 add + add >= x
if add < x-add {
return false
}
add += add
}
// 不能使用除法
z >>= 1
}
return true
}
left, right, ans := 1, IntMax, 0
for left <= right {
// 注意溢出,并且不能使用除法
mid := left + ((right - left) >> 1)
if quickAdd(divisor, mid, dividend) {
ans = mid
// 注意溢出
if mid == IntMax {
break
}
left = mid + 1
} else {
right = mid - 1
}
}
if rev {
return -ans
}
return ans
}
|