Number Max: Write a method that finds the maximum of two numbers. You should not use if-else or any other comparison operator.
Hints: #473, #513, #707, #728
解法
不用任何if-else和比较操作符，给你两个数字，让你返回最大的那一个。换句话说就是禁止使用if-else、三元条件式、大于小于等于。那么剩下的就只有数学运算符和bit运算符。
如果给你一个k，当a > b时k=1，否则k=0。那么怎么得到a和b中的最大值呢？可以这样：
1
2
3
|
max = b + (a - b) * k
OR
max = a * k + b * (not k)
|
那如何创建k呢？
如果a > b，那么 a - b > 0，那么它的符号位是0，向右shift 31 bit，和1 XOR一下，得到k = 1
如果a < b，那么 a - b < 0，那么它的符号位是1，向右shift 31 bit，和1 XOR一下，得到k = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// n >= 0 return 1, else return 0
public int sign(int n) {
return flip(n >> 31);
}
public int flip(int n) {
return n ^ 1;
}
public int max(int a, int b) {
int k = sign(a - b);
int q = flip(k);
return a * k + b * q;
}
|
但是要注意a - b可能会造成int的bit溢出，导致符号位变成1。比如a=Integer.MAX_VALUE b=-20，a < 0且b > 0时，a - b虽然会有溢出，但是符号位不会变。
所以：
1
2
3
4
5
6
7
8
9
|
符号位=1代表整数，符号位=0代表负数
if (a和b的符号位不同) {
// a < 0, b > 0时, a - b符号位应该是0，和a相同
// a > 0, b < 0时, a - b符号位应该是1，和a相同
符号位 = a的符号位
} else {
符号位 = (a - b)的符号位
}
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int max(int a, int b) {
int c = a - b;
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
// sign a和sign b符号是否不同，相同得到0，不同得到1
int use_sa = sa ^ sb;
// sign a和sign b符号是否相同，相同得到1，不同得到0
int use_sc = flip(sa ^ sb);
int k = sa * use_sa + sc * use_sc;
int q = flip(k);
return a * k + b * q;
}
|
评论