LeetCode 面试题 16.07. 最大数值
题目描述
题意分析
不使用比较运算符或条件分支，返回两个 32 位有符号整数
a、b中的较大值。要同时处理负数、相等值及整数边界，不能依赖可能溢出的 32 位减法判断大小。
解法：宽差符号位 + 算术选择
核心思路
[!blue]
差值
d = a - b为负，说明应选择b；否则选择a。但两个 32 位整数的差可能超出 32 位范围，因此必须先把输入转成 64 位整数，再做减法。差值范围最多到正负2^32 - 1，64 位整数足以准确保存其符号。对这个有符号差值算术右移 63 位，非负数得到 0，负数得到所有位为 1 的 -1。再与 1 按位与，就得到选择位
k：差值为负时是 1，其余情况是 0。这里用位运算取得符号，不需要比较或分支。
k ^ 1恰好是互补的选择位，所以a * (k ^ 1) + b * k在k = 0时只保留a，在k = 1时只保留b。两个乘积分别是原输入或零，求和时也只有一个输入被保留，不会因为合成结果产生额外溢出。两数相等时选择a同样正确。
解题步骤
- 将两个输入转为
long/int64后相减。- 将差值算术右移 63 位，再与 1，得到零一选择位
k。- 返回
a * (k ^ 1) + b * k，用互补权重保留较大值。
代码实现
class Solution {
public int maximum(int a, int b) {
// 先扩宽两个输入再相减，符号掩码与一后得到零一选择位。
int k = (int) (((long) a - (long) b) >> 63) & 1;
return a * (k ^ 1) + b * k;
}
}
func maximum(a int, b int) int {
// 先扩宽两个输入再相减，符号掩码与一后得到零一选择位。
k := int(((int64(a) - int64(b)) >> 63) & 1)
return a*(k^1) + b*k
}
复杂度分析
- 时间复杂度：$O(1)$。只执行固定次数的类型转换、位运算和算术运算。
- 空间复杂度：$O(1)$。仅保存一个选择位。
关键点总结
[!green]
- 先扩宽再相减，才能让差值符号真实反映两个输入的大小关系。
- 符号掩码是 0 或 -1，与 1 后才成为可用的零一权重。
- 权重互补，保证结果恰好等于两个输入之一。
易错点总结
[!yellow]
- 在 32 位类型中减完才转成 64 位，已经发生的溢出无法补救。
- 省略
& 1会把 -1 当作权重，得到错误的乘积和。k = 1表示a - b为负，应选择b，不要把两项权重接反。- Go 的参数虽写作
int，安全扩宽的依据仍是本题输入限制为 32 位有符号整数。- 使用带比较条件的三目表达式或
if，不符合题目的运算限制。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！