What is the fastest way to reverse bits for a 32-bit integer?

Use a combination of divide and conquer with masks and shifts, or precompute a lookup table for 8-bit blocks to reduce operations.

Does the input always need to be even in the Reverse Bits problem?

The problem statement guarantees even integers, which simplifies some bit shift calculations, but solutions should still handle all 32 bits.

Can recursive approaches be used without hitting stack limits?

Yes, since the recursion depth is bounded by the fixed 32-bit length, stack usage remains minimal and safe.

What common mistakes should I avoid when reversing bits?

Avoid misaligned shifts, off-by-one swaps, and forgetting to handle all bit segments consistently in iterative or recursive merges.

How does divide and conquer specifically help in Reverse Bits?

It allows breaking the integer into smaller blocks, reversing each independently, and then combining them correctly, reducing mental and operational complexity.

#190

Easy

auto_awesomedivide·conquer·结合·位运算·操作

LeetCode 题解工作台

颠倒二进制位

颠倒给定的 32 位有符号整数的二进制位。示例 1：输入： n = 43261596 输出： 964176192 解释：整数二进制 43261596 00000010100101000001111010011100 964176192 0011100101111000001010010100…

分治位运算

题目描述

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

示例 1：

输入：n = 43261596

输出：964176192

解释：

整数	二进制
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

示例 2：

输入：n = 2147483644

输出：1073741822

解释：

整数	二进制
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

提示：

0 <= n <= 2³¹ - 2
n 为偶数

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

lightbulb

解题思路

方法一：位运算

我们可以从低位到高位，逐个取出 $n$ 的每一位，然后将其放到 $\textit{ans}$ 的对应位置上。

比如，对于第 $i$ 位，我们可以通过 $(n \& 1) \ll (31 - i)$ 来取出 $n$ 的第 $i$ 位，并将其放到 $\textit{ans}$ 的第 $31 - i$ 位上，然后将 $n$ 右移一位。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

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

speed

复杂度分析

指标	值
时间	complexity depends on the chosen approach: iterative and recursive divide-and-conquer methods run in O(1) since the bit length is fixed at 32, while the lookup table method also achieves O(1) with faster constant-time operations. Space complexity varies: iterative uses O(1), recursive uses O(log32)=O(1) stack, and lookup table uses O(256) for precomputation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to recognize bit-level patterns and swap sequences.
question_mark
Look for proper handling of masks and shifts without off-by-one errors.
question_mark
Assess whether the candidate applies divide and conquer to sub-bit blocks correctly.

warning

常见陷阱

外企场景

error
Incorrectly swapping bits without using proper masks leading to wrong output.
error
Forgetting to handle all 32 bits consistently in iterative or recursive steps.
error
Misaligning left and right halves when merging, producing off-by-one bit errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse bits for integers of arbitrary bit lengths, not limited to 32 bits.
arrow_right_alt
Count the number of 1s after reversing bits to combine bit manipulation patterns.
arrow_right_alt
Perform in-place bit reversal for arrays of integers using the same divide and conquer principle.

help

常见问题

外企场景

继续练习

#191 位1的个数 #187 重复的DNA序列 #201 数字范围按位与