LeetCode 面试题 05.07. 配对交换
题目描述
题意分析
把整数二进制表示中的第 0 位与第 1 位、第 2 位与第 3 位……成对交换，返回交换后的整数。下标从最低有效位开始计数，所以要交换的是所有偶数位与其左边相邻的奇数位。
每对中的偶数位都要左移一格，奇数位都要右移一格，移动规律完全相同。因此可以一次取出全部偶数位与全部奇数位，分组移动后再合并，不必逐对处理。
十六进制一位对应四个二进制位：
5对应0101，A对应1010。从最低位编号为零开始看，重复八个5得到保留偶数位的掩码，重复八个A得到保留奇数位的掩码。
解法：奇偶位掩码分组移动
核心思路
[!blue]
num & 0x55555555将所有奇数位清零，只保留原来的偶数位；左移一格后，第2t位恰好落到同一对的第2t+1位。另一组用num & 0xAAAAAAAA只保留奇数位，再右移一格，把第2t+1位送到第2t位。两个源掩码互不重叠，又共同覆盖全部 32 位，所以每个原始位只会被保留一次。移动后的两个目标位置集合仍不重叠，一组只占奇数位，另一组只占偶数位，因此按位或可以直接合并，不会覆盖彼此。每个位置收到的正是原来相邻配对位置的值，这就完成了所有交换。
Java 使用
>>>明确表示右移时补零。题目实际输入范围为[0,2^30-1]，不会涉及符号位；Go 中按掩码保留的奇数位部分也保持非负，右移不会引入高位一。两种实现都只需两次与、两次移位和一次或。
解题步骤
- 用
0x55555555取出偶数位，左移一格。- 用
0xAAAAAAAA取出奇数位，无符号右移一格。- 对两部分按位或，得到每对位置都交换后的结果。
一对位相同时，交换后自然不变；两位不同时，恰好互换一和零。输入为零时两组都为零，无需额外处理。
代码实现
// 偶数位左移，奇数位无符号右移，再合并。
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)$。
关键点总结
[!green]
- 掩码根据源位置分组：偶数位左移，奇数位右移。
- 源位置各被选中一次，目标位置又互不重叠，保证合并不丢位也不重复。
- 二进制
0101和1010可以直接推导出两个十六进制掩码。
易错点总结
[!yellow]
- 位号从最低位的零开始，不能把字符串显示方向当作编号方向。
- 若改成先移位再掩码，目标掩码也要对应调整，不能原样照搬当前两个源掩码。
- Java 的
>>>与>>对负数有不同含义；本题输入范围没有负数，解释时应区分运算语义与实际输入边界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 190. 颠倒二进制位 | 简单 | 同样移动位的位置，原题反转全部32位，本题只交换相邻两位。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！