给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和mod运算符。返回被除数dividend除以除数divisor得到的商。整数除法的结果应当截去（truncate）其小数部分。
- 例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
解法：
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136object TwoSumDivide {
def main(args: Array[String]): Unit = {
println(divide(10, 3))
println(divide(7, -3))
println(divide(3, -3))
println(divide(3, 3))
println(divide(-2147483648, -1))
println(divide(-2147483648, 2))
println(divide(Int.MaxValue, 1))
println(divide(Int.MaxValue, -1))
println("-----------------------------------------------------")
println(divide1(10, 3))
println(divide1(7, -3))
println(divide1(3, -3))
println(divide1(3, 3))
println(divide1(-2147483648, -1))
println(divide1(-2147483648, 2))
println(divide1(Int.MaxValue, 1))
println(divide1(Int.MaxValue, -1))
println("-----------------------------------------------------")
println(divide2(10, 3))
println(divide2(7, -3))
println(divide2(3, -3))
println(divide2(3, 3))
println(divide2(-2147483648, -1))
println(divide2(-2147483648, 2))
println(divide2(Int.MaxValue, 1))
println(divide2(Int.MaxValue, -1))
println(divide2(2147483647, 3))
}
/**
* 不断2倍逼近
*/
def divide2(dividend: Int, divisor: Int): Int = {
val sign = if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) true else false
if (Math.abs(dividend) == Math.abs(divisor)) return if (dividend == divisor) 1 else -1
if (dividend != Int.MinValue && Math.abs(dividend) < Math.abs(divisor)) return 0
if (dividend == Int.MinValue && divisor == -1) return Int.MaxValue
var absDividend = -Math.abs(dividend)
val absDivisor = -Math.abs(divisor)
var result = 0
while (absDividend <= absDivisor) {
var i = absDivisor
var c = 1
while (i + i < 0 && i + i > absDividend) {
i += i
c += c
}
result += c
absDividend = absDividend - i
}
if (sign) result else -result
}
/**
* 都转为正数，用加法不断的逼近
*/
def divide(dividend: Int, divisor: Int): Int = {
val sign = if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) true else false
if (Math.abs(dividend) == Math.abs(divisor)) return if (dividend == divisor) 1 else -1
if (dividend != Int.MinValue && Math.abs(dividend) < Math.abs(divisor)) return 0
var k = 0
if (dividend == Int.MinValue) {
if (divisor == -1) {
return Int.MaxValue
}
val absDivisor = -Math.abs(divisor)
var sum = absDivisor
while (sum < 0) {
k += 1
sum += absDivisor
}
if (sign) k else -k
} else {
val absDividend = Math.abs(dividend)
val absDivisor = Math.abs(divisor)
var sum = absDivisor
while (sum <= absDividend && sum > 0) {
k += 1
sum += absDivisor
}
if (sign) k else -k
}
}
/**
* 都转为负数，每次扩大2倍去逼近 降为log(n)
*/
def divide1(dividend: Int, divisor: Int): Int = {
val sign = if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) true else false
if (Math.abs(dividend) == Math.abs(divisor)) return if (dividend == divisor) 1 else -1
if (dividend != Int.MinValue && Math.abs(dividend) < Math.abs(divisor)) return 0
if (dividend == Int.MinValue && divisor == -1) return Int.MaxValue
var absDividend = -Math.abs(dividend)
val absDivisor = -Math.abs(divisor)
val nums = new Array[Int](40)
val mutilps = new Array[Int](40)
nums(0) = absDivisor
mutilps(0) = 1
var j = 1
for (j <- 1 until 32) {
if (nums(j - 1) << 1 < 0) {
nums(j) = nums(j - 1) << 1
mutilps(j) = mutilps(j - 1) << 1
}
}
var l = 0
for (i <- 0 until 39) {
if (nums(i) < 0) {
l += 1
}
}
l = l - 1
var result = 0
while (absDividend <= absDivisor) {
while (absDividend <= nums(l)) {
result += mutilps(l)
absDividend -= nums(l)
}
l -= 1
}
if (sign) result else -result
}
}