class Max {
public:
int getMax(int a, int b) {
// write code here
return (((long long)a+b)+((((long long)a-b)^(((long long)a-b)>>63))-(((long long)a-b)>>63)))/2;
}
};
解题思路全解析
这段代码的核心是用数学公式 + 位运算实现“无比较求两个整数的最大值”，全程不使用 if-else、比较运算符（>/<），同时解决了整数溢出问题，是面试中“无比较求最大值”的经典解法。以下分4个层面拆解思路：
一、核心原理：最大值的数学公式（整个代码的根基）
对于任意两个整数 a 和 b，最大值可以通过以下数学公式计算：[\max(a,b) = \frac{a + b + |a - b|}{2}]公式逻辑验证：
- 若
a ≥ b：|a - b| = a - b，代入公式得(a+b +a -b)/2 = a（正确）； - 若
b > a：|a - b| = b - a，代入公式得(a+b +b -a)/2 = b（正确）； - 若
a = b：|a - b| = 0，代入公式得(a+b)/2 = a = b（正确）。
代码的所有逻辑，都是为了安全实现这个公式（重点解决“绝对值计算”和“溢出问题”）。
二、代码分步拆解（逐段解释作用）
我们把代码拆成5个核心部分，逐一说明：
return (((long long)a+b) + ((((long long)a-b) ^ (((long long)a-b)>>63)) - (((long long)a-b)>>63))) / 2;
| 把
强制转为64位整数
，再和
相加，避免
溢出（比如
时，
超32位int范围）。 |
| 计算
的差值
，同样转64位避免溢出，记为
。 |
| 获取
的符号位（64位
的符号位在第63位）：<br>- 若
（正数/0），右移63位结果为
；<br>- 若
（负数），右移63位结果为
（64位补码全1）。 |
| 位运算计算 ` |
整体
| 代入最大值公式，完成 `(a+b+ |
三、关键细节（新手最容易踩坑的点）
1. 为什么用 long long 而不是 int？
int 是32位，取值范围是 -2^31 ~ 2^31-1，如果 a 和 b 都是大数（比如 a=2^31-1, b=1），a+b 会超出 int 范围，触发溢出（数值变成负数），导致计算错误。long long 是64位，取值范围极大（-2^63 ~ 2^63-1），能容纳 int 范围内任意两个数的和/差，彻底避免溢出。
2. 为什么用 >>63 而不是 >>31？
因为我们把 a-b 转成了64位 long long，64位整数的符号位在第63位（32位int的符号位在第31位）。如果用 >>31，64位负数右移31位得到的不是 -1，而是 0xFFFFFFFF80000000，会导致绝对值计算错误。
四、测试用例验证（直观理解逻辑）
用例1：正数场景 a=5, b=3
x = (long long)5 - 3 = 2（正数）；x>>63 = 2>>63 = 0；- 绝对值计算：
(2^0)-0 = 2； - 最大值计算：
(5+3 +2)/2 = 10/2 = 5（正确）。
用例2：负数场景 a=-5, b=3
x = (long long)-5 -3 = -8（负数）；x>>63 = -8>>63 = -1；- 绝对值计算：
(-8 ^ -1) - (-1) = 7 +1 =8； - 最大值计算：
(-5+3 +8)/2 =6/2=3（正确）。
用例3：溢出场景 a=2147483647, b=1
x = 2147483647 -1 = 2147483646（正数）；a+b = 2147483648（long long能存，无溢出）；- 最大值计算：
(2147483648 + 2147483646)/2 = 2147483647（正确）。
核心思路总结
- 底层逻辑：用数学公式
(a+b+|a-b|)/2绕开比较操作，实现最大值计算； - 位运算技巧：通过
x>>63获取符号位，再用(x^sign)-sign计算绝对值（兼容正负）； - 工程细节：用
long long解决32位int的溢出问题，保证计算安全； - 关键坑点：64位整数必须用
>>63取符号位，32位用>>31，否则符号判断错误。
这段代码是“数学公式 + 位运算 + 溢出处理”的结合，既满足“无比较”的要求，又保证了工程上的正确性，是面试中该题的最优解之一。
京公网安备 11010502036488号