LeetCode 面试题 05.06. 整数转换
目录
题目描述
题意分析
给定两个 32 位整数
A和B，每次只能翻转其中一个二进制位，求把A变成B最少需要翻转多少位。每一位彼此独立：相同位不需要动，不同位必须且只需翻一次。因此答案就是两数二进制表示的汉明距离，也就是“对应位不同”的位置数。
输入可能是负数，必须按 32 位补码比较。负号不是一个额外字符，符号位就是第 31 位；所以不要转成带
-的二进制字符串，也不要只扫描到最高非零位。
解法：异或标记差异位 + 位计数
核心思路
异或的真值表恰好对应题意：相同位异或为 0，不同位异或为 1。因此
A ^ B中每一个 1，都代表一个无法省掉的翻转；统计这些 1 即可。Java 的
Integer.bitCount明确定义为统计 32 位补码中的 1。Go 的int宽度与平台有关，所以先把异或结果转换为uint32，再用bits.OnesCount32，才能严格对应题目的 32 位语义。若面试要求手写位计数，可以使用 Brian Kernighan 技巧：反复执行
x &= x - 1，每次消去最低位的一个 1，循环次数恰好等于答案。
解题步骤
- 计算
diff = A ^ B，让所有不同位变成 1、相同位变成 0。- 对
diff做 32 位 bit count。- 返回 1 的数量；不同位之间互不影响，不需要模拟实际翻转过程。
以
A = 29 = 0b11101、B = 15 = 0b01111为例，A ^ B = 0b10010，只有第 4 位和第 1 位为 1，因此最少翻转 2 次。任何方案都必须改这两位，而各翻一次就能达到B，下界与构造相等。
代码实现
// 异或结果中的 1 恰好对应需要翻转的位置。
class Solution {
public int convertInteger(int A, int B) {
return Integer.bitCount(A ^ B);
}
}
// 固定转成 uint32，避免 Go 的 int 宽度影响 32 位题意。
func convertInteger(A int, B int) int {
return bits.OnesCount32(uint32(A ^ B))
}
复杂度分析
- 时间复杂度：32 位宽度固定，
bitCount为 $O(1)$；若把位宽记为w，普通逐位统计是 $O(w)$，Kernighan 写法是 $O(k)$，k为差异位数。- 空间复杂度：$O(1)$。
关键点总结
- “两个值有多少位不同”应直接联想到异或；异或负责定位差异，bit count 负责计数。
- 正确性可以用逐位下界说明：每个不同位至少翻一次，相同位无需翻；把全部不同位各翻一次正好达到目标。
- 面试追问通常是手写 bit count，以及负数如何处理。回答时要明确“按 32 位补码统计”，Go 版因此使用
uint32。
易错点总结
- 统计
A和B各自的 1 再取差值：A = 1(01)、B = 2(10)的 1 数都为 1，差值是 0，但实际有两位不同，答案是 2。- 用
A - B的绝对值推断翻转数：数值距离与汉明距离无关，7(111)到8(1000)数值只差 1，却有 4 位不同。- Go 里直接调用与机器字长绑定的计数函数：在 64 位环境中，负数会按 64 位补码统计，结果比题目要求多 32；应固定为
uint32。- 把负数转成带负号的字符串再逐字符比较：会丢失补码高位，且把
-错当成数据。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 191. 位1的个数 | 简单 | 位计数 |
| 338. 比特位计数 | 简单 | 位计数 |
| 461. 汉明距离 | 简单 | 位计数 |
| 477. 汉明距离总和 | 中等 | 位计数 |
| LCR 003. 比特位计数 | 简单 | 位计数 |
| 剑指 Offer 15. 二进制中1的个数 | 简单 | 位计数 |