Approach Summary
For each of 32 bits: shift result left, OR in LSB of n, shift n right. After 32 iterations result holds reversed bits.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 32-Bit Sequential Shift & Accumulation | O(1) [32 iterations] | O(1) | Extract the LSB of n, shift it to mirrored position (31 - i), and combine via bitwise OR. |
| 2 Approach 2: Divide and Conquer / Parallel Bitmask Swapping (Optimal) | O(1) [5 operations] | O(1) | Swap 16-bit blocks, then 8-bit, 4-bit, 2-bit, and 1-bit pairs in 5 constant-time parallel mask operations. |
Step 1: Baseline
Approach 1: 32-Bit Sequential Shift & Accumulation
Time: O(1) [32 iterations]
Space: O(1)
Loop exactly 32 times. On each iteration i, extract the lowest bit using lsb = (n & 1). Shift this bit to its target mirror slot reverseLsb = lsb << (31 - i) and merge into result with result | reverseLsb. Then shift n right by 1 (using unsigned >>> in Java/JS). This guarantees every bit is mapped to its exact symmetric index.
Approach 1: 32-Bit Sequential Shift & Accumulation Implementation
Approach 1: 32-Bit Sequential Shift & Accumulation
public class Solution {
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
int lsb = (n & 1);
int reverseLsb = lsb << (31 - i);
result = result | reverseLsb;
n = n >>> 1;
}
return result;
}
}class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for (int i = 0; i < 32; i++) {
int lsb = (n & 1);
int reverseLsb = lsb << (31 - i);
result = result | reverseLsb;
n = n >> 1;
}
return result;
}
};class Solution:
def reverseBits(self, n: int) -> int:
result = 0
for i in range(32):
lsb = n & 1
reverse_lsb = lsb << (31 - i)
result |= reverse_lsb
n >>= 1
return resultfunction reverseBits(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
const lsb = n & 1;
const reverseLsb = lsb << (31 - i);
result = result | reverseLsb;
n = n >>> 1;
}
return result >>> 0;
} Step 2: Most Optimized
Approach 2: Divide and Conquer / Parallel Bitmask Swapping (Optimal)
Time: O(1) [5 operations]
Space: O(1)
Similar to merge sort on bits, we swap the top 16 bits with bottom 16 bits: n = (n >> 16) | (n << 16). Next, swap 8-bit blocks using mask 0xFF00FF00. Next, swap 4-bit nibbles using mask 0xF0F0F0F0. Then 2-bit pairs with 0xCCCCCCCC, and finally adjacent 1-bit pairs with 0xAAAAAAAA. This executes in 5 instructions without any branching or loop overhead.
Approach 2: Divide and Conquer / Parallel Bitmask Swapping (Optimal) Implementation
Approach 2: Divide and Conquer / Parallel Bitmask Swapping (Optimal)
public class Solution {
public int reverseBits(int n) {
n = ((n >>> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
n = ((n >>> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
n = ((n >>> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
return n;
}
}class Solution {
public:
uint32_t reverseBits(uint32_t n) {
n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
return n;
}
};class Solution:
def reverseBits(self, n: int) -> int:
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 nfunction reverseBits(n) {
n = ((n >>> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
n = ((n >>> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
n = ((n >>> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
return n >>> 0;
}Edge Cases to Watch
- n = 0 (binary all 0s; reversed result is 0)
- n = 1 (binary 000...001; reversed is 2^31 = 2147483648)
- n = 0xFFFFFFFF (all 1s; reversed result is 0xFFFFFFFF)
- Alternating bits (0xAAAAAAAA or 0x55555555; inverted patterns)
Algorithmic Pattern
View Pattern Guide →
Master the Bit Manipulation Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Bit Manipulation pattern.
Framework: Bit Manipulation • Interview Prep: Tested at FAANG •
Explore all Bit Manipulation problems & invariants →
How to Recognize This Pattern
- Reverse all 32 bits of an unsigned integer
- Process bit-by-bit: extract LSB, append to result
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(1)
Tags
Divide and Conquer Bit Manipulation
Frequently Asked Questions
What is the optimal time and space complexity for Reverse Bits?
The optimal solution for Reverse Bits achieves O(1) runtime complexity and requires O(1) auxiliary space. Time complexity is O(1) because both approaches execute a fixed, bounded number of operations (32 iterations for bit-by-bit; 5 operations for divide-and-conquer). Space complexity is O(1) auxiliary space as only fixed integer registers are used.
How do I identify that Reverse Bits requires the Bit Manipulation pattern?
In technical interviews, look for key problem signals: Reverse all 32 bits of an unsigned integer; Process bit-by-bit: extract LSB, append to result. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Bit Manipulation strategy.
What critical edge cases must be handled in Reverse Bits?
Essential edge cases to verify include: n = 0 (binary all 0s; reversed result is 0); n = 1 (binary 000...001; reversed is 2^31 = 2147483648); n = 0xFFFFFFFF (all 1s; reversed result is 0xFFFFFFFF); Alternating bits (0xAAAAAAAA or 0x55555555; inverted patterns). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Reverse Bits?
Reverse Bits is a Easy-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Apple, Amazon.