面试题 05.07. 配对交换
题目描述
配对交换。编写程序,交换某个整数的奇数位和偶数位,尽量使用较少的指令(也就是说,位0与位1交换,位2与位3交换,以此类推)。
示例1:
输入:num = 2(或者0b10) 输出 1 (或者 0b01)
示例2:
输入:num = 3 输出:3
提示:
num
的范围在[0, 2^30 - 1]之间,不会发生整数溢出。
解法
方法一:位运算
我们可以将 $\text{num}$ 与 $\text{0x55555555}$ 进行与运算,得到的结果是 $\text{num}$ 的偶数位,然后将其左移一位。再将 $\text{num}$ 与 $\text{0xaaaaaaaa}$ 进行与运算,得到的结果是 $\text{num}$ 的奇数位,然后将其右移一位。最后将两个结果进行或运算,即可得到答案。
时间复杂度 $O(1)$,空间复杂度 $O(1)$。
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 |
|