程序员面试金典 - 面试题 05.07. 配对交换

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例 1:

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

示例 2:

• 输入：num = 3
• 输出：3

提示:

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

题目思考

1. 可以使用什么位运算来尽可能减少操作指令数目?

解决方案

思路

• 根据题目描述, 很自然想到可以分为奇数变偶数和偶数变奇数两部分求解
• 对于奇数变偶数, 我们可以将原来的偶数位清 0, 然后右移一位
• 对于偶数变奇数, 我们可以将原来的奇数位清 0, 然后左移一位
• 最后再将两部分求或并起来(|)即可
• 至于具体实现, 我们可以引入一个标记 0x55555555, 对应的二进制就是 01010101...
• 这样在奇数变偶数时, 我们先右移一位, 将旧的奇数位变成新的偶数位, 然后再与这个标记求与, 从而清空新的奇数位 (即旧的偶数位)
• 而在偶数变奇数时, 我们先与这个标记求与, 清空旧的奇数位, 然后再左移一位, 从而将旧的偶数位变成新的奇数位

复杂度

• 时间复杂度 O(1): 只需要几次常数级别的位运算操作
• 空间复杂度 O(1): 只使用了几个变量

代码

Python 3

class Solution:
    def exchangeBits(self, num: int) -> int:
        # 奇数变偶数 | 偶数变奇数
        # 原数字右移一位, 再与0x55555555(即01010101...)求与, 从而实现原偶数位清0, 原奇数位变偶数
        # 原数字与0x55555555求与, 然后左移一位, 从而实现原奇数位清0, 原偶数位变奇数
        # 最终两者求或, 即得到奇偶交换后的数字
        return (num >> 1) & 0x55555555 | ((num & 0x55555555) << 1)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊