190. 颠倒二进制位
题目描述
输入整数 n，把它看作 32 位二进制数（不足 32 位时高位补 0）。
将这 32 位的顺序前后颠倒：最低位变成最高位，最高位变成最低位。返回颠倒后得到的整数。
数据保证 n 是偶数，因此颠倒后最高位为 0，结果仍是非负数。
输入：n = 43261596 输出：964176192
解释：43261596 的 32 位二进制为 00000010100101000001111010011100，倒过来是 00111001011110000010100101000000，即 964176192。
输入：n = 2147483644 输出：1073741822
解释：01111111111111111111111111111100 倒过来为 00111111111111111111111111111110，即 1073741822。
数据范围
0 <= n <= 2^31 - 2n是偶数。
进阶：如果这个函数会被调用很多次，可以怎样优化？
解题思路：逐位颠倒
像“倒出一叠盘子”一样逐位搬运：循环 32 次，每次用 n & 1 取出 n 的最低位，把 res 左移一位后放到 res 的最低位上，再把 n 右移一位。先取出的低位在之后会被不断左移，最终到达高位，完成颠倒。
为什么正确
执行 i 次后，res 的低 i 位恰好是 n 原来的低 i 位倒序；n 剩下尚未处理的 32 - i 位。
复杂度分析
时间 O(32)；空间 O(1)。
易错点
必须固定循环 32 次而不是 while n，否则 n 的高位 0 不会被搬过去，结果少了左移；Java/JS 要用无符号右移 >>>，C++ 用 unsigned，避免负数右移补 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for _ in range(32):
res = (res << 1) | (n & 1)
n >>= 1
return resclass Solution {
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
res = (res << 1) | (n & 1);
n >>>= 1;
}
return res;
}
}class Solution {
public:
int reverseBits(int n) {
unsigned res = 0, x = n;
for (int i = 0; i < 32; i++) {
res = (res << 1) | (x & 1);
x >>= 1;
}
return (int)res;
}
};func reverseBits(n int) int {
res := 0
for i := 0; i < 32; i++ {
res = (res << 1) | (n & 1)
n >>= 1
}
return res
}var reverseBits = function(n) {
let res = 0;
for (let i = 0; i < 32; i++) {
res = (res << 1) | (n & 1);
n >>>= 1;
}
return res;
};function reverseBits(n: number): number {
let res = 0;
for (let i = 0; i < 32; i++) {
res = (res << 1) | (n & 1);
n >>>= 1;
}
return res;
}其他解法
逐位颠倒循环 32 次，每次搬一位；位运算分治每层并行交换所有块，5 层完成。
解法 2：位运算分治 时间 O(log 32)，空间 O(1)
翻转 32 位等于交换高低 16 位，再在每个 16 位内交换高低 8 位，依次到 4 位、2 位、1 位。每一层用掩码同时取出所有奇数块和偶数块，分别移位后合并，一共 5 层。掩码依次是 0x55555555、0x33333333、0x0f0f0f0f、0x00ff00ff，最后一层直接交换高低 16 位。
没有循环，只有常数次位运算，适合频繁调用的场景。掩码不直观，需要理解分治的层次。
class Solution:
def reverseBits(self, n: int) -> int:
n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
n = ((n >> 16) & 0xffff) | ((n & 0xffff) << 16)
return nclass Solution {
public int reverseBits(int n) {
n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
n = (n >>> 16) | (n << 16);
return n;
}
}class Solution {
public:
int reverseBits(int value) {
unsigned n = value;
n = ((n >> 1) & 0x55555555u) | ((n & 0x55555555u) << 1);
n = ((n >> 2) & 0x33333333u) | ((n & 0x33333333u) << 2);
n = ((n >> 4) & 0x0f0f0f0fu) | ((n & 0x0f0f0f0fu) << 4);
n = ((n >> 8) & 0x00ff00ffu) | ((n & 0x00ff00ffu) << 8);
n = (n >> 16) | (n << 16);
return (int)n;
}
};func reverseBits(num int) int {
n := uint32(num)
n = n>>1&0x55555555 | n&0x55555555<<1
n = n>>2&0x33333333 | n&0x33333333<<2
n = n>>4&0x0f0f0f0f | n&0x0f0f0f0f<<4
n = n>>8&0x00ff00ff | n&0x00ff00ff<<8
n = n>>16 | n<<16
return int(n)
}var reverseBits = function(n) {
n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
n = (n >>> 16) | (n << 16);
return n;
};function reverseBits(n: number): number {
n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
n = (n >>> 16) | (n << 16);
return n;
}