LeetCode 面试题 16.07. 最大数值

约 9 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动 程序员面试金典（第 6 版）
标签
数学 位运算 脑筋急转弯
目录

题目描述

✅ 面试题 16.07. 最大数值

题意分析

给定两个整数 a 和 b，返回其中较大的那个。看起来是最简单不过的一行代码，但题目加了一条硬约束：不得使用 if-else 及比较运算符。也就是说 >、<、>=、<=、==、三目运算符、Math.max 全部被禁用。

这条约束把题目从"求最大值"改造成了"如何在不做分支的前提下选出两个候选之一"。能用的工具只剩算术运算和位运算，于是解题的方向被锁死为：造出一个只取 0 或 1 的选择位 k，再用算术把它变成一个二选一的开关。

第二个必须读出的信号是取值范围：a 和 b 都是 32 位有符号整数，可以取到 -2^31 和 2^31 - 1。这意味着 a - b 在 32 位下会溢出（例如 a = 2^31 - 1、b = -2^31 时差值是 $2^{32}-1$，远超 int 范围），而符号位恰恰是我们要提取的东西——一旦溢出，符号位就是错的，整个方法直接崩塌。所以差值必须在更宽的类型里计算。

边界上要覆盖：a == b（返回哪个都对，但要保证不返回 0 之类的第三值）；一正一负跨越 int 边界；两者都是负数；以及 a、b 取到 int 极值。

解法：位运算压缩状态

核心思路

因为分支被禁，第一反应是把"选 a 还是选 b"写成一个加权求和：

\[\text{answer} = a \cdot (1 - k) + b \cdot k\]

其中 k 是一个只取 0 或 1 的选择位：k = 0 时式子退化成 a，k = 1 时退化成 b。这样只要能算出 k，就完全绕开了分支。剩下的问题变成：如何在不比较的前提下，让 k 在 a < b 时取 1、否则取 0。

关键观察是补码的符号位就是一次比较的结果。在补码表示下，一个数是负数当且仅当它的最高位为 1。因此 a - b 的符号位天然编码了"a 是否小于 b"这个布尔值——不需要写任何比较运算符，符号位已经把答案算好了。

提取符号位的标准手法是算术右移到底再取最低位。对 64 位有符号数 d = a - b 做 d >> 63：算术右移会用符号位填充高位，所以 d < 0 时结果全 1（即 -1），d >= 0 时结果全 0。再 & 1 就把 -1 收成 1、0 保持 0，恰好得到我们要的选择位 k。

至于 1 - k，代码里写成 k ^ 1。异或 1 是对 0/1 取反的标准写法：0 ^ 1 = 1，1 ^ 1 = 0，与 1 - k 完全等价，但避免了一次减法、也更能体现"这是一个位开关"的意图。

最后是溢出。Java 的 int 只有 32 位，a - b 可能溢出导致符号位翻转，所以必须先把两个操作数提升成 long 再相减，右移的位数也随之变成 63。Go 的 int 在 64 位平台上本身就是 64 位，而输入只有 32 位量级，差值不可能溢出，所以直接 (a - b) >> 63 就是安全的——这也是两份代码看起来不对称的原因，不是笔误，而是类型宽度不同带来的必要差异。

顺带确认一下 k == 0（即 a >= b）时 b * k = 0 不会出问题：b 无论多大，乘 0 都是 0；a * (k ^ 1) = a * 1 = a 也不会溢出，因为结果就是原值。两个分支的乘法都不会引入新的溢出风险。

解题步骤

  • 把 a、b 提升到 64 位后相减。这是防溢出的关键一步：a = 2147483647、b = -2147483648 时，32 位下的 a - b 会绕回成 -1，符号位是 1，导致算法认为 a < b 而选错。提升到 long 后差值是 4294967295，符号位正确为 0。
  • 算术右移 63 位提取符号位。必须用算术右移（Java 的 >>、Go 的 >> 作用在有符号类型上）而不是逻辑右移（Java 的 >>>）：逻辑右移用 0 填充高位，负数右移 63 位得到的是 1 而不是 -1，虽然 & 1 之后结果碰巧相同，但语义上依赖的是"符号位被复制到最低位"，用算术右移意图更明确、也便于推广到"取符号掩码"的其他场景。
  • & 1 把掩码压成 0/1 的选择位 k。右移后得到的是 -1（全 1）或 0，直接拿来乘会把结果取反，必须先收成 0/1。
  • 用 a * (k ^ 1) + b * k 合成答案。k ^ 1 是 k 的 0/1 取反；两项中恰好有一项被乘 0 抹掉、另一项被乘 1 保留，实现了无分支的二选一。加号在这里不是"求和"，而是"把被抹掉的那项当作 0 拼进来"。

以 a = 1、b = 2 走一遍：(long) 1 - (long) 2 = -1，二进制补码是全 1。-1 >> 63 仍是 -1（算术右移用符号位 1 填充），转成 int 后 & 1 得到 k = 1。代入公式：1 * (1 ^ 1) + 2 * 1 = 1 * 0 + 2 = 2。返回 2，正确。

以 a = 2、b = 1 走一遍：差值 1，最高位是 0，1 >> 63 = 0，k = 0。代入：2 * (0 ^ 1) + 1 * 0 = 2 * 1 + 0 = 2。返回 2，正确。

以 a = 5、b = 5 走一遍：差值 0，符号位 0，k = 0，返回 5 * 1 + 5 * 0 = 5。相等时取 a，符合题意。

以 a = -2147483648、b = 2147483647 走一遍（跨 int 边界）：若不提升类型，32 位下 a - b 会绕回成 1，符号位为 0 得到 k = 0，错误地返回 a = -2147483648。提升到 long 后差值是 -4294967295，符号位为 1，k = 1，返回 b = 2147483647，正确。这一步正是溢出防护唯一能被观察到的地方，也是本题真正的考点。

反向再走一次 a = 2147483647、b = -2147483648：long 差值 4294967295 为正，k = 0，返回 a = 2147483647，正确。

代码实现

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 := (a - b) >> 63 & 1
    return a*(k^1) + b*k
}

复杂度分析

  • 时间复杂度：$O(1)$。全程只有一次减法、一次移位、两次按位与/异或和两次乘加，指令条数与输入大小无关，没有任何循环或递归。
  • 空间复杂度：$O(1)$。只用了一个 int 变量 k 和几个临时寄存器值，不依赖任何随输入增长的存储。

关键点总结

  • 禁用分支时，把"条件"变成一个 0/1 的选择位，再用算术合成结果。answer = x * (1 - k) + y * k 是这类题的万能骨架；把它记牢，遇到"不许用 if""不许用比较"的题就能直接套。
  • 补码的符号位就是一次免费的比较。d >> (w - 1) 得到的全 0 / 全 1 掩码，是"无分支编程"里最常用的原语：& 1 得到 0/1 开关，直接拿掩码去 & 还能实现"条件清零"。
  • 提取符号位之前必须先确认差值不会溢出。这是本题唯一真正的陷阱：a - b 在原类型下溢出会让符号位彻底失真，而且只在跨越取值边界的极端用例上暴露，普通测试很难发现。凡是"用差的符号做判断"的写法，都要先把操作数提升到更宽的类型。
  • k ^ 1 与 1 - k 等价，但前者更表意。在 0/1 域上异或 1 就是逻辑非，写成位运算能让"这是一个开关"的意图一眼可见，也和整段代码的位运算风格统一。
  • 面试视角：主动说清"为什么 Java 要转 long 而 Go 不用"。这个不对称正是面试官期待的追问点——答案是 Java 的 int 固定 32 位、差值会溢出，而 Go 的 int 在 64 位平台是 64 位、容得下两个 32 位数的差。能主动交代类型宽度对位运算正确性的影响，比写出这几行代码更能体现基本功。此外可以补一句更"标准"的无溢出写法：先分别取 a、b 的符号位，同号时用差值符号、异号时直接由符号决定，代价是逻辑更长但不依赖宽类型。

易错点总结

  • 错误写法：int k = ((a - b) >> 31) & 1;（不提升类型，直接在 32 位下取符号位） → 用例 a = -2147483648、b = 2147483647：32 位下 a - b 溢出绕回成 1，符号位为 0，k = 0，返回 a = -2147483648，正确答案是 2147483647。
  • 错误写法：Java 里写 (long) (a - b)（先在 int 里减完再转 long） → 用例同上：溢出发生在转换之前，转成 long 只是把已经错误的 1 变宽，符号位依旧错。必须是 (long) a - (long) b，让减法本身发生在 64 位里。
  • 错误写法：用 >>> 逻辑右移并右移 31 位 → 用例 a = 1、b = 2，且操作数是 32 位：(a - b) >>> 31 得到 1 看似正确，但一旦按本题写成 64 位再 >>> 63，对负数得到的是 1、对正数是 0，结果碰巧也对；真正的问题是这种写法在需要"全 1 掩码"的变体里会失效。位运算题里符号位提取应统一用算术右移。
  • 错误写法：return a * k + b * (k ^ 1);（两项的开关接反） → 用例 a = 1、b = 2：k = 1，返回 1 * 1 + 2 * 0 = 1，正确答案是 2。k = 1 代表 a < b，此时该保留的是 b。
  • 错误写法：忘记 & 1，直接写 int k = (int) (((long) a - (long) b) >> 63); → 用例 a = 1、b = 2：k = -1，返回 1 * (-1 ^ 1) + 2 * (-1) = 1 * (-2) - 2 = -4，完全错误。右移得到的是掩码不是开关，必须先收成 0/1。
  • 错误写法：用 Math.abs 拼出 (a + b + Math.abs(a - b)) / 2 → 用例 a = 2147483647、b = -2147483648：a + b 与 a - b 双双溢出，结果是垃圾值；即使换成 long，Math.abs 在 Long.MIN_VALUE 上还会返回负数。这个"数学技巧"看似绕开了比较，实际把溢出风险放大了一倍。
  • 错误写法：用三目运算符 return a > b ? a : b; → 虽然本地能跑出正确结果，但直接违反"不得使用 if-else 及比较运算符"的题目约束，面试里等同于没做。
  • 错误写法：Go 里写成 k := (a - b) >> 31 & 1 → 用例 a = 1、b = 2：a - b = -1，右移 31 位在 64 位 int 下得到的仍是 -1，& 1 后是 1，结果碰巧正确；但换成 a = -1、b = 0 之外的某些值时，右移位数与类型宽度不匹配的写法会让"取符号位"的推理不再成立。移位位数必须等于类型位宽减一。
  • 错误写法：Go 里写 k := (a - b) >> 63 & 1 但把优先级理解成 (a-b) >> (63 & 1) → 若按这个误解显式加括号写成 (a - b) >> (63 & 1)，即右移 1 位：用例 a = 1、b = 2 得到 -1 >> 1 = -1，k 变成 -1，结果完全错。Go 里 >> 与 & 同级、自左向右结合，原写法等价于 ((a-b) >> 63) & 1，是正确的。
  • 错误写法：用 k 去做数组下标 return new int[]{a, b}[k]; → 这在多数判题下能通过，但引入了 $O(1)$ 的堆分配、也让"无分支"的意图被数组访问掩盖；更重要的是，一旦 k 因为前面的写法错误取到 -1，就变成数组越界异常而不是一个错误答案，反而更难定位。

相似题目

题目 难度 考察点
面试题 16.01. 交换数字 中等 不用临时变量交换两数，靠异或的自反性而非符号位
面试题 17.01. 不用加号的加法 简单 禁用加号，用异或求无进位和、与加移位求进位并迭代到收敛
371. 两整数之和 中等 与上题同模型的主站版本，重点在负数补码下的循环终止条件
面试题 05.06. 整数转换 简单 求两数二进制差异位数，考的是异或后的 popcount
面试题 05.07. 配对交换 简单 用奇偶位掩码分离后错位移动，是"掩码 + 移位"的另一种组合