使用位运算技巧比较两个数中较大的数
作者：
Grey
原文地址：
题目要求
如何不要用任何比较判断符（
>
,
==
,
<
），返回两个 32 位整数中较大的那个。
主要思路
方法1（不考虑溢出）
要比较 a 和 b 的大小，因为不能用比较符号，我们可以通过 a – b 的符号位来判断，如果 a – b 的符号位是 1，说明 a – b < 0，则 a 小，否则 a 大或者 a 和 b 相等。
如何判断一个数的符号位是 0 还是 1 ？
由于是 32 位整数，所以可以将一个数右移 31 位，然后和 1 相与(
&
)，如果得到 1，则这个数是负数，如果得到 0，则这个数是正数。
举个具体例子，如果要求 a 和 b 谁大，我们可以先通过
((a - b) >> 31) & 1
得到一个值，如果这个值是 1 ，说明 a 小，否则 a 大或者 a 和 b 相等。
由于不能出现比较符号，所以无法使用如下代码
return ((a - b) >> 31) & 1 == 1?b:a;
也无法使用如下代码
if (((a - b) >> 31) & 1 == 1){
return b;
}
return a;
但是我们可以巧妙利用
((a - b) >> 31) & 1
结果去构造一个公式，这个公式可以在
((a - b) >> 31) & 1 == 1
情况下得到 b， 在
((a - b) >> 31) & 1 == 0
情况下得到 a。
我们可以利用一个反转函数
public int flip(int n) {
return n ^ 1;
}
这个函数的作用就是，当
n == 1
时，返回 0，当
n == 0
时，返回 1，我们将判断符号的结果
flip
一次，如下代码
public static int sign(int n) {
return flip((n >> 31) & 1);
}
这个方法的作用就是
当符号位是 1 的时候，返回 0，符号位是 0 的时候，返回 1。
经过
flip
后，
sign(a - b)
如果得到 1， 则：
a - b > 0
，则返回 a。
sign(a - b)
如果得到 0， 则：
a - b <= 0
，则返回 b。
公式可以定义成
sign(a - b) * a + flip(sign(a - b)) * b
主函数直接做如下调用
public static int getMax1(int a, int b) {
int c = a - b;
//当符号位是 1 的时候，scA = 0，符号位是 0 的时候，scA = 1。
int scA = sign(c);
// scA = 1 时，scB = 0，scA = 0时，scB = 1
int scB = flip(scA);
// 如果 scA = 0，说明 b 大，直接返回b
// 如果 scA = 1，说明 a 大，直接返回a
return a * scA + b * scB;
}
这个方法没有考虑溢出的情况，比如
a = 2147483647;
b = -2147480000;
a - b
直接就溢出了，后面的算法就都不适用了。
方法2（考虑溢出情况）
那我们可以先比较 a 与 b 两个数的符号，
会有如下几种情况：
情况1：符号不同，则直接返回符号为正的那个数。
情况2：如果符号相同，则这种情况下,
a - b
的值绝对不会溢出，那么就看 c 的符号（c为正返回a，c为负返回b）
方法2的核心代码如下
int c = a - b;
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
int difSab = sa ^ sb;
int sameSab = flip(difSab);
int returnA = difSab * sa + sameSab * sc;
int returnB = flip(returnA);
return a * returnA + b * returnB;
其中:
int difSab = sa ^ sb
就是判断 a 和 b 的符号是否一样，如果
difSab == 1
，则 a 和 b 符号一样，如果
difSab == 0
，则 a 和 b 符号不一样。
只有当
difSab == 0
的时候，要考虑 c 的符号。因为
difSab == 0
,所以
int returnA = 0 * sa + 1 * sc;
，即
int returnA = sc
,如果 sc 为 1，说明 c 的符号是 0，则
a - b > 0
，返回 a 即可，否则返回 b。
方法1和方法2的完整代码和测试代码如下：
// 不要用任何比较判断，返回两个数中较大的数
public class Code_GetMaxWithoutCompare {
public static int flip(int n) {
return n ^ 1;
}
public static int sign(int n) {
return flip((n >> 31) & 1);
}
public static int getMax1(int a, int b) {
int c = a - b;
int scA = sign(c);
int scB = flip(scA);
return a * scA + b * scB;
}
public static int getMax2(int a, int b) {
int c = a - b;
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
int difSab = sa ^ sb;
int sameSab = flip(difSab);
int returnA = difSab * sa + sameSab * sc;
int returnB = flip(returnA);
return a * returnA + b * returnB;
}
public static void main(String[] args) {
int a = -16;
int b = -19;
System.out.println(getMax1(a, b));
System.out.println(getMax2(a, b));
a = 2147483647;
b = -2147480000;
System.out.println(getMax1(a, b)); // wrong answer because of overflow
System.out.println(getMax2(a, b));
}
}
更多
参考资料