标签: 位运算
难度: Easy
配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。
示例1:
输入：num = 2（或者0b10） 输出 1 (或者 0b01)
示例2:
输入：num = 3 输出：3
提示:
num的范围在[0, 2^30 - 1]之间，不会发生整数溢出。
Submission
运行时间: 22 ms
内存: 16.1 MB
class Solution:
def exchangeBits(self, num: int) -> int:
return ((num & 0x55555555) << 1) | ((num >> 1) & 0x55555555)
Explain
题解的核心思路是利用位运算来高效地交换整数中的奇数位与偶数位。首先，通过与掩码0x55555555相与，可以将整数num中的所有奇数位置零（因为0x55555555在二进制中表示为01010101...，它的奇数位是0，偶数位是1）。然后，将这个结果左移一位，就将原本的奇数位移到了偶数位的位置。接着，通过将num右移一位再与0x55555555相与，可以得到原始偶数位移动到奇数位的结果。最后，将这两个结果使用或操作合并起来，就实现了奇数位和偶数位的交换。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def exchangeBits(self, num: int) -> int:
# 使用掩码0x55555555选取偶数位
even_bits = num & 0x55555555
# 将偶数位左移，准备放到奇数位上
even_bits_shifted = even_bits << 1
# 使用掩码0x55555555选取奇数位，并右移至偶数位
odd_bits_shifted = (num >> 1) & 0x55555555
# 将调整后的奇数位和偶数位组合起来
return even_bits_shifted | odd_bits_shifted
Explore
掩码0x55555555在二进制中表示为01010101...，这种模式的特点是在偶数位上是1，而在奇数位上是0。选择这种掩码可以有效地通过与操作（AND）选取出整数中的所有偶数位，因为偶数位与1的AND操作保持不变，而奇数位与0的AND操作则变为0。这使得掩码0x55555555成为选取和处理偶数位的理想工具，而对于位交换的操作，我们需要分别处理奇数位和偶数位，因此这种掩码非常适用。
在这个位交换的算法中，将偶数位左移和奇数位右移确实需要考虑整数num的最高位的影响。对于32位整数，最右边的位（奇数位）右移时会消失，而最左边的位（在某些情况下可能是最高的偶数位）左移时会进入下一个更高的位。然而，由于我们使用的是无符号整数操作（假设整数是无符号的），左移偶数位时最高位（31位）会被移出，并且会自动填充0。右移奇数位时，也会从左边自动填充0。因此，这种位移操作不会影响到整数的符号位或造成溢出，而是仅仅实现了位的交换功能。
是的，这种做法确保了原始的奇数位和偶数位不会相互影响。通过首先将偶数位和奇数位分别通过掩码和位移操作独立处理，我们得到了两个数字：一个只包含原始偶数位现在移动到奇数位的结果，另一个只包含原始奇数位现在移动到偶数位的结果。由于这两个操作结果分别只占据了整数的奇数位或偶数位，他们在进行或操作（OR）合并时不会有重叠，因此可以无冲突地合并。这保证了位交换的正确性和原始位的独立性。