LeetCode 190.颠倒二进制位 | 从暴力解法到位运算魔法
前言
这道题的核心是32 位二进制位反转，我最初用数组 + 短除法实现，虽然能跑但有符号、精度、前导 0 隐患；学习官方位运算解法后，才真正理解二进制操作的精髓
题目 ★★☆☆☆
190. 颠倒二进制位 颠倒给定的 32 位有符号整数的二进制位。
例如：
输入：00000000 00000000 00000000 00000001
输出：10000000 00000000 00000000 00000000
我的思路
我最先想到的思路是利用进制转换和数组来实现，其核心步骤为：十进制数转换为二进制数 → 颠倒二进制数 → 二进制数转换为十进制数。
- 十进制数转换为二进制数：可以利用短除法实现
- 颠倒二进制数：利用数组实现，将短除法得到的二进制的每一位存放在数组中，再从不同方向遍历数组即可得到颠倒后的二进制数
- 二进制数转换为十进制数：直接利用数学上的转换方式
代码
class Solution { public: int reverseBits(int n) { int arr[32]; int index = 0; int a = n; // 被除数 // 短除法：十进制转换为二进制 while (a != 0) { arr[index++] = a % 2; a /= 2; } index = 31; // 从0下标遍历数组得到颠倒后的二进制数 // 二进制转换为十进制 int res = 0; // 颠倒后的十进制数 int b = 0; // 次分 while (index >= 0) { res += arr[index--] * pow(2, b++); } return res; } };复杂度
时间复杂度：O(1)。固定的循环次数。
空间复杂度：O(1)。固定的数组大小。
存在问题
虽然通过了所有测试用例（能通过的原因：测试用例友好 + 数组自动补 0），但仍存在以下问题：
- int 是有符号数，负数会出错
- 短除法无法处理高位 0，会丢失前导 0，导致结果错误
- 使用 pow(2,b) 浮点运算，会产生精度错误
官方题解
方法一：逐位颠倒
核心思想
把 32 位整数一位一位取出来，再一位一位放到反转后的位置
位运算
利用 & 和 | 符号进行操作：
- &：实现取数操作。n & 1——取最后一位：n = 101101，1 = 000001，n & 1 → 000001 → 只保留最后一位
- |：实现放数操作。rev |=：rev = 100000，新位= 001000，两种相 | → rev= 101000 → 直接拼进去，不覆盖原来的
逐位颠倒步骤
- 结果
rev初始化为 0 - 循环 32 次（固定 32 位）
- 取出 n 最低位：
bit = n & 1 - 把这一位移到它反转后的位置：
bit << (31 - i) - 用
|把这一位合并到rev - n 右移一位，删掉已处理的最低位
- 循环结束，
rev就是答案
代码
class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t rev = 0; // 最终反转结果 for (int i = 0; i < 32; i++) { // 1. 取出 n 的最低位（0 或 1） int bit = n & 1; // 2. 将这一位放到反转后的位置（第i位 → 第31-i位） rev |= bit << (31 - i); // 3. n 右移一位，处理下一位 n = n >> 1; } return rev; } };复杂度
时间复杂度：O(1)
空间复杂度：O(1)
方法二：位运算分治
核心思想
不循环，直接分组交换，把 32 位分成：16 位 ↔ 16 位 → 8 位 ↔ 8 位 → 4 位 ↔ 4 位 → 2 位 ↔ 2 位 → 1 位 ↔ 1 位
每一步都用掩码 + 位移完成交换，最终实现整体反转。
分治过程
- 交换相邻 1 位（奇偶位交换）
- 交换相邻 2 位
- 交换相邻 4 位
- 交换相邻 8 位
- 交换相邻 16 位
经过 5 步交换，32 位全部反转
掩码含义
M1 = 0x55555555→ 奇偶位交换（1 位一组）M2 = 0x33333333→ 2 位一组交换M4 = 0x0f0f0f0f→ 4 位一组交换M8 = 0x00ff00ff→ 8 位一组交换
代码
class Solution { private: const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101 const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011 const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111 const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111 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; } };复杂度
时间复杂度：O(1)
空间复杂度：O(1)
