leetcode/lcci/05.07.Exchange/README.md

comments	difficulty	edit_url
true	简单	https://github.com/doocs/leetcode/edit/main/lcci/05.07.Exchange/README.md

面试题 05.07. 配对交换

English Version

题目描述

配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。

示例1:

 输入：num = 2（或者0b10）
 输出 1 (或者 0b01)

示例2:

 输入：num = 3
 输出：3

提示:

1. num的范围在[0, 2^30 - 1]之间，不会发生整数溢出。

解法

方法一：位运算

我们可以将 \textit{num} 与 \textit{0x55555555} 进行与运算，得到的结果是 \textit{num} 的偶数位，然后将其左移一位。再将 \textit{num} 与 \textit{0xaaaaaaaa} 进行与运算，得到的结果是 \textit{num} 的奇数位，然后将其右移一位。最后将两个结果进行或运算，即可得到答案。

时间复杂度 O(1)，空间复杂度 O(1)。

Python3

class Solution:
    def exchangeBits(self, num: int) -> int:
        return ((num & 0x55555555) << 1) | ((num & 0xAAAAAAAA) >> 1)

Java

class Solution {
    public int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa)) >> 1;
    }
}

C++

class Solution {
public:
    int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa)) >> 1;
    }
};

Go

func exchangeBits(num int) int {
	return ((num & 0x55555555) << 1) | (num&0xaaaaaaaa)>>1
}

TypeScript

function exchangeBits(num: number): number {
    return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
}

Rust

impl Solution {
    pub fn exchange_bits(num: i32) -> i32 {
        let num = num as u32;
        (((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)) as i32
    }
}

Swift

class Solution {
    func exchangeBits(_ num: Int) -> Int {
        let oddShifted = (num & 0x55555555) << 1

        let evenShifted = (num & 0xaaaaaaaa) >> 1

        return oddShifted | evenShifted
    }
}