配对交换

难度:

标签:

题目描述

Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).

Example1:

 Input: num = 2（0b10）
 Output 1 (0b01)

Example2:

 Input: num = 3
 Output: 3

Note:

0 <= num <= 2^30 - 1
The result integer fits into 32-bit integer.

代码结果

运行时间: 22 ms, 内存: 16.1 MB

/*
 * 思路：
 * 使用与普通Java实现相同的思路，但这里演示如何通过Java Stream API处理一系列数字的交换。
 */
import java.util.stream.IntStream;

public class PairwiseSwapStream {
    public int swapOddEvenBits(int num) {
        int oddBits = (num & 0xAAAAAAAA) >>> 1; // 提取奇数位并右移
        int evenBits = (num & 0x55555555) << 1; // 提取偶数位并左移
        return oddBits | evenBits; // 合并结果
    }
    public static void main(String[] args) {
        PairwiseSwapStream pss = new PairwiseSwapStream();
        IntStream.of(2, 3).map(pss::swapOddEvenBits).forEach(System.out::println); // 输出1和3
    }
}

解释

方法:

题解的核心思路是利用位运算来高效地交换整数中的奇数位与偶数位。首先，通过与掩码0x55555555相与，可以将整数num中的所有奇数位置零（因为0x55555555在二进制中表示为01010101...，它的奇数位是0，偶数位是1）。然后，将这个结果左移一位，就将原本的奇数位移到了偶数位的位置。接着，通过将num右移一位再与0x55555555相与，可以得到原始偶数位移动到奇数位的结果。最后，将这两个结果使用或操作合并起来，就实现了奇数位和偶数位的交换。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么选择使用掩码0x55555555来操作位交换，这个掩码的二进制表示中的特点是什么？

▷

掩码0x55555555在二进制中表示为01010101...，这种模式的特点是在偶数位上是1，而在奇数位上是0。选择这种掩码可以有效地通过与操作（AND）选取出整数中的所有偶数位，因为偶数位与1的AND操作保持不变，而奇数位与0的AND操作则变为0。这使得掩码0x55555555成为选取和处理偶数位的理想工具，而对于位交换的操作，我们需要分别处理奇数位和偶数位，因此这种掩码非常适用。

🦆

在将偶数位左移和奇数位右移时，是否考虑了整数num的最高位会如何受到影响？

▷

在这个位交换的算法中，将偶数位左移和奇数位右移确实需要考虑整数num的最高位的影响。对于32位整数，最右边的位（奇数位）右移时会消失，而最左边的位（在某些情况下可能是最高的偶数位）左移时会进入下一个更高的位。然而，由于我们使用的是无符号整数操作（假设整数是无符号的），左移偶数位时最高位（31位）会被移出，并且会自动填充0。右移奇数位时，也会从左边自动填充0。因此，这种位移操作不会影响到整数的符号位或造成溢出，而是仅仅实现了位的交换功能。

🦆

你提到的方法中提及，通过位移和掩码操作后，直接进行或操作以合并结果。这种做法是否确保了原始的奇数位和偶数位不会相互影响？

▷

是的，这种做法确保了原始的奇数位和偶数位不会相互影响。通过首先将偶数位和奇数位分别通过掩码和位移操作独立处理，我们得到了两个数字：一个只包含原始偶数位现在移动到奇数位的结果，另一个只包含原始奇数位现在移动到偶数位的结果。由于这两个操作结果分别只占据了整数的奇数位或偶数位，他们在进行或操作（OR）合并时不会有重叠，因此可以无冲突地合并。这保证了位交换的正确性和原始位的独立性。

配对交换

题目描述

代码结果

解释

代码细节讲解

相关问题