LeetCode 190. 颠倒二进制位【C语言详解 + 多种解法】

一、题目描述

给定一个 32 位整数 n，请将其 二进制位进行翻转，即最低位变为最高位，最高位变为最低位。

例如：

输入：n = 43261596
输出：964176192

二进制变化如下：

原数
00000010100101000001111010011100

翻转后
00111001011110000010100101000000

二、解法一：逐位翻转（最经典解法）

思路

由于整数共有 32 位，我们可以逐位处理：

例如：

n = abcdefgh

result = hgfedcba

C语言实现

int reverseBits(int n) {

unsigned int result = 0;

for(int i = 0; i < 32; i++)
{
result <<= 1; // 左移腾出位置
result |= (n & 1); // 取最低位加入
n >>= 1; // 右移一位
}

return result;
}

复杂度分析

时间复杂度：O(32) ≈ O(1)
空间复杂度：O(1)

因为二进制位数固定为 32 位。

三、解法二：按位映射

思路

把 n 的 第 i 位

移动到 第 31-i 位

公式：

((n >> i) & 1) << (31 – i)

步骤：

C语言实现

int reverseBits(int n) {

unsigned int result = 0;

for(int i = 0; i < 32; i++)
{
result |= ((n >> i) & 1) << (31 – i);
}

return result;
}

复杂度分析

时间复杂度：O(32)
空间复杂度：O(1)

四、解法三：位运算分治（最高效）

这种方法通过 交换不同大小的位块 来实现翻转。

步骤：

交换 16 位
交换 8 位
交换 4 位
交换 2 位
交换 1 位

示意：

abcdefgh → efghabcd

C语言实现

int reverseBits(int n) {

unsigned int x = n;

x = (x >> 16) | (x << 16);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);

return x;
}

复杂度分析

时间复杂度：O(1)
空间复杂度：O(1)

这种方法是 位运算优化技巧，效率最高。

五、进阶：多次调用如何优化？

如果函数被 调用很多次，可以使用 查表法（Lookup Table）。

思路：

示意：

32 bit
= 8 + 8 + 8 + 8

这样可以实现：

O(1) 查询

适用于：

• 高频调用

• 位运算库

• 网络协议处理

六、总结

面试推荐写法：

逐位翻转

原因：

• 思路清晰

• 不容易写错

• 面试官最常见答案