不使用比较运算符-如何获取两个整数的最大值

在这里插入图片描述这道题如果用 a-b 的符号判断，在两数处于比较极端的情况下可能会发生整数溢出。

比如当 a 是Integer.MIN_VALUE（-2147483648）、b 是Integer.MAX_VALUE（2147483647）时，a-b 会溢出成正数，导致错误地认为 a 比 b 大。

本文接下来介绍一种新颖的解法。

代码逻辑

1.flip：翻转0和1

1
2
3
4


// 必须保证n是0或1，返回翻转后的值
public static int flip(int n) {
    return n ^ 1; // 异或1：0^1=1，1^1=0
}

2.sign：判断数字符号

int 是 32 位，最高位（第 31 位）是 “符号位”——0 表示非负（正数或 0），1 表示负数。经过flip 翻转后非负数从 0→1，负数从 1→0。

1
2
3
4


// 非负数返回1，负数返回0
public static int sign(int n) {
    return flip(n >>> 31); // 无符号右移31位后翻转
}

3.核心方法getMax

当 a 和 b 符号不同时，直接根据符号判断；当符号相同时，再用 a-b 的符号判断。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23



public static int getMax(int a, int b) {
    int c = a - b; 
    
    // 计算a、b、c的符号
    int sa = sign(a); // a非负→1，负→0
    int sb = sign(b); // b非负→1，负→0
    int sc = sign(c); // c非负→1，负→0（c可能溢出）
    
    // 判断a和b的符号是否不同：diffAB=1（不同），diffAB=0（相同）
    int diffAB = sa ^ sb; // 不同为1，相同为0
    // 判断a和b的符号是否相同：相同为1，不同为0
    int sameAB = flip(diffAB);
    
    // 确定returnA（选a的权重：1选a，0选b）
    // 符号不同时（diffAB=1）：选非负的那个（sa=1→a非负，选a）
    // 符号相同时（sameAB=1）：选c非负的那个（sc=1→a>=b，选a）
    int returnA = diffAB * sa + sameAB * sc;
    int returnB = flip(returnA); // 选b的权重
    
    // 返回最大值
    return a * returnA + b * returnB;
}

完整代码

链接：https://pan.quark.cn/s/7efcb9d22a2f 提取码：jdgT