LeetCode 面试题 05.06. 整数转换
题目描述
题意分析
给定两个 32 位整数
A和B，每次只能翻转其中一个二进制位，求把A变成B最少需要翻转多少位。比较的是两个数的二进制位，不是数值之间的距离。目标只要求对应位置变得相同，各位翻转互不影响，所以可以先标出哪些位置不同，再统计这些位置的数量。
输入可能是负数，必须按 32 位补码比较。负号不是一个额外字符，符号位就是第 31 位；所以不要转成带
-的二进制字符串，也不要只扫描到最高非零位。
解法：异或标记差异位 + 位计数
核心思路
[!blue]
按位异或在两个输入位相同时得到
0，不同时得到1。因此A ^ B是一个差异掩码：其中每个一的位置都需要修改，每个零的位置已经与目标一致。设差异掩码中有
d个一。任何转换方案都至少要修改这d个不同位置一次，因此翻转数不可能少于d；把它们各翻一次，同时保留相同位置，又恰好能得到B。这个下界能够达到，所以最少次数就是差异掩码中一的数量，无需模拟翻转过程。Java 的
int固定为 32 位，Integer.bitCount直接统计这 32 位补码。Go 的int可能更宽，先将异或结果转成uint32，只保留题目要求的低 32 位，再用bits.OnesCount32计数。这样即使异或结果为负，也不会把更宽机器字中的符号扩展位算进去。
解题步骤
- 计算
diff = A ^ B，让所有不同位变成 1、相同位变成 0。- 对
diff做 32 位 bit count。- 返回 1 的数量；不同位之间互不影响，不需要模拟实际翻转过程。
A与B完全相同时，异或为零，答案为0；所有对应位都不同时，答案达到上界32。正数与负数都使用同一套位比较，不需要按正负分支。
代码实现
// 异或结果中的 1 恰好对应需要翻转的位置。
class Solution {
public int convertInteger(int A, int B) {
return Integer.bitCount(A ^ B);
}
}
import (
"math/bits"
)
// 固定转成 uint32，避免 Go 的 int 宽度影响 32 位题意。
func convertInteger(A int, B int) int {
return bits.OnesCount32(uint32(A ^ B))
}
复杂度分析
- 时间复杂度：$O(1)$，对固定 32 位整数执行异或与位计数。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- “两个值有多少位不同”应直接联想到异或；异或负责定位差异，bit count 负责计数。
- 正确性可以用逐位下界说明：每个不同位至少翻一次，相同位无需翻；把全部不同位各翻一次正好达到目标。
- 位宽属于题意的一部分，Go 版先转成
uint32，使统计范围与 Java 一致。
易错点总结
[!yellow]
- 分别统计两数的一数量再作差，会丢失这些一所在的位置，不能得到差异位数。
- 数值之差涉及进位或借位，与逐位翻转次数无关。
- Go 若按机器字长直接统计负的异或结果，会把额外的符号扩展位计入，必须固定到 32 位。
- 负数的文字表示中的负号不属于数据位，应按补码而不是带负号的字符串比较。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 191. 位1的个数 | 简单 | 原题统计一个数中的1，本题先异或把不同位转成1再计数。 |
| 477. 汉明距离总和 | 中等 | 同样逐位分析汉明距离，原题汇总所有数对，可按每位0和1的数量相乘计数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！