Vue.js

Appearance

On this page

实战：颠倒二进制位 ​

反转一个 32 位无符号整数的二进制位。

问题描述 ​

LeetCode 190. Reverse Bits

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

示例：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)

解法一：逐位构建 ​

javascript
function reverseBits(n) {
  let result = 0;
  
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;
  }
  
  return result >>> 0;  // 转为无符号数
}

执行过程 ​

n = 101 (简化示例)

i=0: result=0, n&1=1, result=1, n=10
i=1: result=10, n&1=0, result=10, n=1
i=2: result=100, n&1=1, result=101, n=0

结果：101 (实际要补到32位)

解法二：分治 ​

类似归并排序的思想，逐步交换：

javascript
function reverseBits(n) {
  n = ((n & 0xffff0000) >>> 16) | ((n & 0x0000ffff) << 16);
  n = ((n & 0xff00ff00) >>> 8)  | ((n & 0x00ff00ff) << 8);
  n = ((n & 0xf0f0f0f0) >>> 4)  | ((n & 0x0f0f0f0f) << 4);
  n = ((n & 0xcccccccc) >>> 2)  | ((n & 0x33333333) << 2);
  n = ((n & 0xaaaaaaaa) >>> 1)  | ((n & 0x55555555) << 1);
  return n >>> 0;
}

分治过程 ​

原始：1234 5678

第1步：交换高低16位 → 5678 1234
第2步：交换8位块    → 6587 2143
第3步：交换4位块    → 8765 4321
...

为什么用 >>> 0？ ​

JavaScript 的位运算结果是 32 位有符号整数，>>> 0 把它转成无符号数。

详细执行过程 ​

以 n = 43261596（二进制 00000010100101000001111010011100）为例：

逐位翻转过程（简化展示）：

初始：result = 0, n = 43261596

循环过程中：
- 每次从 n 取出最低位
- 左移 result 并加入该位
- 右移 n

32 轮后：
result = 964176192

翻转前后对比：

原始：00000010100101000001111010011100
翻转：00111001011110000010100101000000

边界情况 ​

javascript
// 全 0
reverseBits(0);  // 0

// 全 1
reverseBits(0xFFFFFFFF);  // 4294967295 (还是全 1)

// 只有最高位是 1
reverseBits(0x80000000);  // 1

// 只有最低位是 1
reverseBits(1);  // 2147483648 (0x80000000)

常见错误 ​

错误一：用有符号右移 >> ​

javascript
// 错误：>> 会保留符号位，负数右移会补 1
n = n >> 1;

// 正确：>>> 无符号右移，始终补 0
n = n >>> 1;

错误二：循环次数不足 ​

javascript
// 错误：循环到 n 为 0 就停止
while (n !== 0) {
  // 可能不足 32 次，高位会丢失
}

// 正确：固定 32 次
for (let i = 0; i < 32; i++) {
  // ...
}

错误三：返回负数 ​

javascript
// JavaScript 位运算结果是 32 位有符号整数
// 如果最高位是 1，结果会是负数

// 解决：用 >>> 0 转为无符号整数
return result >>> 0;

相关题目 ​

题目难度关键点
190. 颠倒二进制位简单本题
191. 位1的个数简单逐位处理
7. 整数反转中等十进制反转
9. 回文数简单反转比较

总结 ​

  1. 逐位法：右移取位，左移填入，32 次循环
  2. 分治法：5 次操作完成，效率更高
  3. 关键细节：使用无符号右移 >>>
  4. JavaScript 特殊：>>> 0 转为无符号整数

复杂度 ​

  • 时间：O(1)
  • 空间：O(1)

在 GitHub 上编辑此页