【面试经典150 | 】颠倒二进制位

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【位运算】

---

题目来源

190. 颠倒二进制位

---

题目解读

将给定的 32 位无符号整数的二进制位进行颠倒。

---

解题思路

方法一：逐位颠倒

n 是一个 32 位的二进制数，我们从低位到高位枚举每一位，将其放置到答案 res 的合适位置。比如 n 的二进制位的第 i 位（从低位往高位数）放置到 res 的第 31 - i 位。当前枚举的比特位为当前 n & 1，在枚举完成当前位后，更新 n >>= 1 为下一个枚举做准备。

实现代码

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 0; i < 32; ++i)
        {
            int lst = n & 1;
            lst <<= (31-i);
            ans |= lst;
            n >>= 1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析

时间复杂度：$O(logn)$。

空间复杂度：$O(1)$。

方法二：分治

还有一种分治的方法来实现 32 位无符号整数的二进制数颠倒。分治法又分为两种：

• 自上而下；
• 自下而上。

我们先来看一下自上而下进行分治，自上而下，首先对二进制数每 16 位为一组进行交换，接着是每 8 位一组交换、4 位一组交换、2 位一组交换直至 1 位二进制数为一组进行交换。通过这样的交换之后，就可以实现 32 位无符号整数的二进制数颠倒

怎么实现 16 位二进制数一组进行交换呢？通过位运算啊，将 n 右移 16 位，那么 n 将只会保留高位的 16 位；将 n 左移 16 位，那么 n 将只会保留低位的 16 位； (n >> 16) | (n << 16) 就完成了第一步的 “对二进制数每 16 位为一组进行交换”。

如图所示，我们以 8 位为一组进行交换，n & 0x00ff00ff 就可以得到 1 组和 3 组位置的 8 位二进制数，我们再对 n & 0x00ff00ff 左移八位，就将 1 组和 3 组位置的 8 位二进制数移动到了 0 组和 2 组。我们现将 n 左移 8 位，然后与上 0x00ff00ff 就将 0 组和 2 组位置的 8 位二进制数移动到了 1 组和 3 组。最后将这两种操作或上就完成了以 8 位为一组进行交换。

类似的可以完成以 4、2、1 为一组的交换操作。

以上遍历自上而下的分治方法。自下而上的分治操作就是先以 1 为一组进行交换，然后再分别以 2、4、16 为一组进行交换。需要注意的是每种交换单位对应需要与上的二进制数。

以下代码给出的是自下而上的分治代码，自上而下的分治代码就是自下而上的分治代码顺序颠倒过来。方法二也是 【进阶】的解决方案。

实现代码

class Solution {
private:
    const uint32_t M1 = 0x55555555;
    const uint32_t M2 = 0x33333333;
    const uint32_t M4 = 0x0f0f0f0f;
    const uint32_t M8 = 0x00ff00ff;
public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。