190. Reverse Bits

easyAsked at Intel

Reverse 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

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

Input

n = 00000010100101000001111010011100

Output

964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2

Input

n = 11111111111111111111111111111101

Output

3221225471 (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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Reverse Bits and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →