Bit Manipulation — Reverse Bits
↗ LeetCode: Reverse Bits · Easy · pattern chapter →
Asked atMetaAmazonGoogleAppleMicrosoftAdobe
Reverse the bits of a 32-bit unsigned integer.
Example 1 — n = 0000...1010 (43261596) → 0011...1001 (964176192)
Constraints — 32 bits. Brute bit-by-bit reverse loop is O(32) = 32 ops. Divide-and-conquer swap adjacent / pairs / nibbles / bytes is 12 ops — ~10⁸ reversals/sec.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Bit-by-bit
java
int reverseBits1(int n) {
int r = 0;
for (int i = 0; i < 32; i++) {
r = (r << 1) | (n & 1);
n >>>= 1;
}
return r;
}O(32).
Approach 2 — SWAR parallel bit swap
Insight. Swap adjacent 1-bit groups; then 2-bit; then 4-bit; then 8-bit; then 16-bit halves. Each step is O(1) via bit masks.
java
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;
return n >>> 16 | n << 16;
}Complexity — Time O(1); Space O(1).
Approach 3 — Cache 8-bit chunks
For repeated calls, precompute an int[256] table of reversed bytes.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Bit-by-bit | O(32) | O(1) | baseline |
| SWAR parallel | O(1) | O(1) | canonical |
| Byte cache | O(1) w/ table | O(256) | production |
When to use which
- Interview — SWAR shows constant-time mastery.
- Production — table cache if called in tight loop.
AI Study CompanionBeta
Related problems
- Number of 1 Bits — SWAR popcount
- Reverse Integer
Was this page helpful?
📚 Related problems