Skip to main content

190. Reverse Bits

easy

Reverse the 32 bits of an unsigned integer. The textbook bit-shuffle problem — straightforward shift loop, with a beautiful divide-and-conquer SWAR variant for the optimized follow-up.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Reverse bits of a given 32 bits unsigned integer. Note: 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. Follow up: If this function is called many times, how would you optimize it?

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)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Loop 32 times. In each iteration: shift result left by 1; OR in the lowest bit of n; shift n right by 1.

Hint 2

After the loop result holds the bit-reversed value. Watch unsigned right shift in Java (use >>>).

Hint 3

Follow-up: SWAR divide-and-conquer reverses in O(log 32) operations using shift-and-mask. Swap odd/even bits, then 2-bit groups, then 4-bit, then 8-bit, then 16-bit halves.

Hint 4

Cached lookup: precompute the reverse of each byte (256 entries). Reverse 4 bytes per call. Trades 1KB memory for ~5x speedup.

Solution approach

Reveal approach

Iterative bit-by-bit. Initialize result = 0. Loop 32 times: result = (result << 1) | (n & 1); n >>= 1 (unsigned shift). After 32 iterations, return result. O(1) time (fixed 32 iterations), O(1) space. SWAR variant for the optimization follow-up: n = (n >> 16) | (n << 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 n. Each line swaps pairs at progressively finer granularity. Five lines, branch-free, ~10x faster than the loop.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Reverse Bits and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →