190. Reverse Bits
easyAsked at IntelReverse the bits of a given 32-bit unsigned integer. Intel hardware-SWE loops use this to probe bit-level fluency: every candidate writes the naive shift loop, but the senior signal is the divide-and-conquer mask trick that processes 32 bits in 5 swap stages.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Intel loops.
- Glassdoor (2026-Q1)— Intel Hardware-SWE phone-screen reports list 'reverse the bits of an int' as a recurring 15-minute warm-up.
- GeeksforGeeks (2025-08)— GfG's 'Intel Interview Experience' archive cites bit-reversal as a standard Intel hardware-engineering ask.
- LeetCode discuss (2025-12)— Intel-tagged problem in the company-frequency list with bit-tricks discussion threads.
Problem
Reverse bits of a given 32 bits unsigned integer. Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
Constraints
The input must be a binary string of length 32.
Examples
Example 1
n = 00000010100101000001111010011100964176192 (00111001011110000010100101000000)Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2
n = 111111111111111111111111111111013221225471 (10111111111111111111111111111111)Approaches
1. Shift-and-OR loop (brute force)
Iterate 32 times. Each step, pop the lowest bit of n and push it as the new lowest bit of result, shifting result left.
- Time
- O(32) = O(1)
- Space
- O(1)
function reverseBitsBrute(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n = n >>> 1;
}
return result >>> 0; // force unsigned
}Tradeoff: Always 32 iterations regardless of input. Simple, no precomputation. The `>>> 0` at the end coerces to a non-negative 32-bit value, which is the JS idiom for 'unsigned' since JS bitwise ops are signed-32-bit.
2. Divide and conquer with masks (optimal)
Swap halves, then quarters, then eighths, then nibbles, then byte-pairs, then bits-within-bytes. Five mask-based swap stages process all 32 bits in O(1) but with constant 5 instead of 32.
- Time
- O(1)
- Space
- O(1)
function reverseBits(n) {
// Swap consecutive bit pairs
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
// Swap consecutive nibbles
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
// Swap consecutive byte halves
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
// Swap consecutive bytes
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
// Swap halves of the 32-bit int
n = (n >>> 16) | (n << 16);
return n >>> 0;
}Tradeoff: Same Big-O as the loop but ~6x fewer ops. The five masks correspond to the binary-tree levels of a butterfly network — same circuit pattern Intel uses in FFT and crypto hardware blocks.
Intel-specific tips
Intel Hardware-SWE interviewers want you to draw the 5-stage swap on the whiteboard. The masks (0xAAAA, 0x5555, 0xCCCC, 0x3333, ...) come straight from RTL textbooks — naming the pattern as 'log2(width) swap stages' or 'butterfly network' is the senior signal. If the interviewer asks 'can you do better than 32 iterations?', the divide-and-conquer answer is what they're fishing for.
Common mistakes
- Using signed right-shift (>>) instead of unsigned (>>>) — for negative-looking 32-bit values the sign-bit gets dragged in and the result is wrong.
- Forgetting the final `>>> 0` to coerce back to a non-negative integer. JS bitwise ops are signed 32-bit so the raw result may print negative.
- Writing all five mask stages but using the wrong mask order — `0xcccccccc` shifts right by 2, `0x33333333` shifts left by 2; mixing them silently passes one test and fails another.
Follow-up questions
An interviewer at Intel may pivot to one of these next:
- Count the set bits of the reversed integer (Hamming Weight follow-up).
- What if you had to do this for a 64-bit integer? (Six stages instead of five.)
- If reverseBits is called many times on the same set of integers, how would you optimize? (Byte-lookup table: precompute reversal of each byte then look up four bytes and reassemble.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does Intel specifically care about reverse-bits?
Bit reversal is the index permutation at the heart of every FFT implementation — including the ones in DSP libraries Intel ships. The candidate who derives the 5-stage swap pattern is the candidate who can later read RTL or understand Intel IPP source.
How does the lookup-table optimization work?
Precompute a 256-entry byte-reversal table once. To reverse a 32-bit integer, split it into 4 bytes, look up each byte's reversal, then concatenate them in reverse byte order. Cuts the per-call work to 4 table lookups + 3 shifts. The constant beats the 5-stage swap if you're amortizing over many calls.
Free learning resources
Curated free links for this problem.