E190.颠倒二进制位

bit manipulation, divide and conquer, https://leetcode.cn/problems/reverse-bits/

颠倒给定的 32 位有符号整数的二进制位。

示例 1：

输入：n = 43261596

输出：964176192

解释：

整数	二进制
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

示例 2：

输入：n = 2147483644

输出：1073741822

解释：

整数	二进制
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

提示：

0 <= n <= 2^31 - 2
n 为偶数

进阶: 如果多次调用这个函数，你将如何优化你的算法？

逻辑：将整数转为二进制字符串，补足 32 位，反转后再转回整数。

方法一：使用格式化字符串（推荐，简洁高效）

python

class Solution:
    def reverseBits(self, n: int) -> int:
        # 格式化为32位二进制字符串，高位补0，然后反转
        return int(f"{n:032b}"[::-1], 2)

优点：

一行完成补零、反转、转整数。
f"{n:032b}" 是 Python 内置的高效格式化方式。
可读性强。

方法二：位运算（更贴近底层，适合面试展示）

python

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            res = (res << 1) | (n & 1)
            n >>= 1
        return res

优点：

不依赖字符串操作，纯位运算，效率更高（尤其在 C/C++/Java 中优势明显）。
展示对位操作的理解。

说明：

每次取 n 的最低位（n & 1），放到 res 的末尾。
res 左移腾出位置，n 右移取出下一位。
循环 32 次确保处理全部位。

总结：

日常开发/LeetCode：用 方法一（格式化 + 切片），简洁清晰。
算法面试/追求极致性能：用 方法二（位运算），体现基本功。

python

class Solution:
    def reverseBits(self, n: int) -> int:
        M1 = 0x55555555  # 01010101010101010101010101010101
        M2 = 0x33333333  # 00110011001100110011001100110011
        M4 = 0x0f0f0f0f  # 00001111000011110000111100001111
        M8 = 0x00ff00ff  # 00000000111111110000000011111111
        
        n = n & 0xFFFFFFFF
        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)) & 0xFFFFFFFF

这段代码实现的是32位二进制逆序，它采用的是一种非常高效的分治法（Divide and Conquer），也常被称为“位级归并排序”思想。
相比于普通的循环 32 次逐位移动，这种方法的时间复杂度是 $O (\log W)$ ，其中 $W$ 是位数（这里 $W = 32$ ，所以只需 5 步操作）。
1. 核心思想：分而治之
如果我们想翻转一个长度为 32 的序列，可以：
交换相邻的 1位组。
交换相邻的 2位组。
交换相邻的 4位组。
交换相邻的 8位组。
交换相邻的 16位 组。
完成这 5 步后，整个 32 位就彻底颠倒过来了。
2. 掩码（Mask）的作用
代码中定义的 M1, M2, M4, M8 是用来定位我们要操作的“块”的：
M1 = 0x55555555: 二进制是 01010101...（奇数位为1）。用于处理 1位组。
M2 = 0x33333333: 二进制是 00110011...（每2位一组，后2位为1）。用于处理 2位组。
M4 = 0x0f0f0f0f: 二进制是 00001111...（每4位一组，后4位为1）。用于处理 4位组。
M8 = 0x00ff00ff: 二进制是 0000000011111111...（每8位一组，后8位为1）。用于处理 8位组。
3. 逐行图解
以 n = (n >> 1 & M1) | ((n & M1) << 1) 为例：
(n & M1) << 1: 把所有位于“偶数位”的数字提取出来，向左移动一位，移到奇数位。
n >> 1 & M1: 把所有位于“奇数位”的数字向右移动一位，移到偶数位。
|: 合并两者。效果是：相邻的两位互换了位置。
演示（简化为8位）：
假设 n = 10 11 01 00
交换相邻 1 位：10 11 01 00 -> 01 11 10 00
交换相邻 2 位：0111 1000 -> 1101 0010
交换相邻 4 位：11010010 -> 00101101 (完成逆序)
4. 代码步骤拆解
python
# 1. 确保是32位无符号数
n = n & 0xFFFFFFFF 

# 2. 交换相邻的 1 位
# 原理：ab cd ef gh -> ba dc fe hg
n = (n >> 1 & M1) | ((n & M1) << 1)

# 3. 交换相邻的 2 位
# 原理：[ba][dc] [fe][hg] -> [dc][ba] [hg][fe]
n = (n >> 2 & M2) | ((n & M2) << 2)

# 4. 交换相邻的 4 位
# 原理：[dcba][hgfe] -> [hgfe][dcba]
n = (n >> 4 & M4) | ((n & M4) << 4)

# 5. 交换相邻的 8 位
n = (n >> 8 & M8) | ((n & M8) << 8)

# 6. 交换相邻的 16 位 (高16位和低16位互换)
# 最后一步不需要掩码，因为 16+16 正好是 32 位
return ((n >> 16) | (n << 16)) & 0xFFFFFFFF
5. 为什么这么做？
性能极高：不需要写 for i in range(32)。对于 CPU 来说，位运算（与、或、移位）是非常基础且极快的指令。
并行思想：这种方法实际上是在同一时间“批量”处理了 16 对、8 对、4 对、2 对、1 对位的交换。
适用场景：在嵌入式开发、图形学、加密算法或对性能要求极高的底层驱动中，这种位操作技巧非常经典。
总结
这段代码是用位运算实现的分治算法，通过不断成倍扩大交换单位（1->2->4->8->16），最终在 5 步内完成了 32 位二进制的左右翻转。

E190.颠倒二进制位 ​

E190.颠倒二进制位