Operations: Write methods to implement the multiply, subtract, and divide operations for integers.The results of all of these are integers. Use only the add operator.
Hints: #572, #600, #613, #648
解法
用加法实现减、乘、除。
减法
A - B = A + (-B)
如果B是正数，那么-B = invertBits(B) + 1。
如果B是负数，那么-B = invertBits(B - 1)。这个是二进制正数负数的表现形式。
1
2
3
4
5
6
7
8
9
|
public int negate(int v) {
if (v == 0) {
return 0;
}
if (v > 0) {
return (~v) + 1;
}
return ~(v + negate(1));
}
|
所以减法：
1
2
3
|
public int minus(int a, int b) {
return a + negate(b);
}
|
乘法
就是连续加几次，要注意负数的问题。
两个数符号相同结果为正、符号不同结果为负。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int multiply(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
int num1 = a > 0 ? a : negate(a);
int count = b > 0 ? b : negate(b);
if (num1 < count) {
// 乘号右边的数字更小一点会循环更少
return multiply(b, a);
}
int result = 0;
for (int i = 0; i < count; i++) {
result += num1;
}
if (a < 0 && b > 0) {
return negate(result);
}
if (a > 0 && b < 0) {
return negate(result);
}
return result;
}
|
除法
除法：5 / 2 = 2，其实就是5一直减 2，减到余数小于2为止，减了几次就是结果。比如 5 - 2 = 3, 3 - 2 = 1，减了两次，所以 5 / 2 = 2。
关键是负数的处理，可以先把两边都变成正数，返回时再改变符号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int divide(int a, int b) {
if (b == 0) {
throw new Exception("/ 0 error");
}
if (a == 0) {
return 0;
}
int num1 = a > 0 ? a : negate(a);
int num2 = b > 0 ? b : negate(b);
int result = 0;
while (num1 > num2) {
num1 = minus(num1, num2);
result++;
}
if (a < 0 && b > 0) {
return negate(result);
}
if (a > 0 && b < 0) {
return negate(result);
}
return result;
}
|
评论