LeetCode 面试题 05.07. 配对交换
目录
题目描述
题意分析
把整数二进制表示中的第 0 位与第 1 位、第 2 位与第 3 位……成对交换，返回交换后的整数。下标从最低有效位开始计数，所以要交换的是所有偶数位与其左边相邻的奇数位。
逐对读取再写回当然可行，但需要循环和多次分支。所有偶数位可以被同一个掩码一次取出，所有奇数位也一样；分组后整体移动一格再合并，正好完成全部配对交换。
32 位交替掩码分别是
0x55555555（二进制0101...，保留偶数位）和0xAAAAAAAA（二进制1010...，保留奇数位）。Java 中右移奇数位应使用无符号右移，避免符号扩展污染高位。
解法：奇偶位掩码分组移动
核心思路
num & 0x55555555只留下原来的偶数位，把它左移一格后，每一位恰好落到同一对的奇数位置。num & 0xAAAAAAAA只留下原来的奇数位，把它无符号右移一格后，恰好落到偶数位置。两组移动后的 1 不会落在同一位置：前一组只占奇数位，后一组只占偶数位，因此用按位或合并不会产生冲突。每个原始位被且只被一个掩码保留，也不会丢位或重复。
这比逐对循环更适合作为面试答案：两次与、两次移位、一次或就完成固定 32 位上的所有交换，掩码的含义也可以直接从最低四位
0101/1010推出来，而不必死记十六进制常量。
解题步骤
- 用
0x55555555取出偶数位，左移一格。- 用
0xAAAAAAAA取出奇数位，无符号右移一格。- 对两部分按位或，得到每对位置都交换后的结果。
以
num = 10 = 0b1010为例。偶数位部分为0000，左移后仍为0000；奇数位部分为1010，右移后得到0101，结果为 5。逐对看也是(10)(10) → (01)(01)。
代码实现
// 偶数位左移，奇数位无符号右移，再合并。
class Solution {
public int exchangeBits(int num) {
return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
}
}
// 偶数位左移，奇数位右移，再合并。
func exchangeBits(num int) int {
return ((num & 0x55555555) << 1) | (num&0xaaaaaaaa)>>1
}
复杂度分析
- 时间复杂度：$O(1)$，固定执行常数次位运算，与整数中 1 的个数无关。
- 空间复杂度：$O(1)$。
关键点总结
- 交替位分组问题优先考虑
0x55555555与0xAAAAAAAA；前者保留偶数位，后者保留奇数位。- 先掩码再移动非常重要：它保证被移出的位不会串入相邻分组，也让两部分合并时互不重叠。
- 面试追问若改成 64 位，只需把掩码扩为
0x5555555555555555与0xAAAAAAAAAAAAAAAA，并使用 64 位无符号语义。
易错点总结
- 两个掩码写反或移动方向写反：
num = 2(10)应变成1(01)，若奇数位左移则会得到 4。- 先移动再掩码：边界位可能先被符号扩展或移出，再也无法用掩码恢复。
- Java 对奇数位使用
>>：当最高位参与时会用 1 补高位；>>>才表达“把位模式整体右移”的意图。- 用加法合并却没证明两部分不重叠：本题虽然结果相同，但按位或更直接表达“合并两个互斥位集合”。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 190. 颠倒二进制位 | 简单 | 按固定映射重排 32 个二进制位 |
| 191. 位1的个数 | 简单 | 基础掩码与位计数 |
| 461. 汉明距离 | 简单 | 异或后统计不同位 |
| 面试题 05.06. 整数转换 | 简单 | 与 461 同型，强调 32 位补码语义 |