Skip to main content

190. Reverse Bits

easy

Reverse the bits of a 32-bit unsigned integer. Classic warm-up for shift and mask techniques, with a divide-and-conquer optimization that interviewers love.

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

Problem

Reverse bits of a given 32 bits unsigned integer.

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 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 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

Iterate 32 times: shift result left by 1, OR in the lowest bit of n, then shift n right by 1.

Hint 2

If you'll call this many times on different inputs, cache 8-bit chunks in a 256-entry lookup table.

Hint 3

Or use divide-and-conquer: swap adjacent bits, then adjacent pairs of bits, then nibbles, then bytes, then halves. log(32) = 5 masked swaps total.

Solution approach

Reveal approach

Iterative shift-and-OR. Initialize result = 0. Loop 32 times: result = (result << 1) | (n & 1), then n >>= 1. After 32 iterations, result holds the bit-reversed value. Time O(32) ≈ O(1), space O(1). For the harder follow-up (called many times), use divide-and-conquer with five masked swaps to flip the 32-bit value in log time using fixed-width masks like 0x55555555 (alternating bits), 0x33333333 (pairs), 0x0F0F0F0F (nibbles), 0x00FF00FF (bytes), 0x0000FFFF (halves). Each step swaps adjacent groups of doubling size; final result is the reversed bits in 5 operations.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation
  • divide-and-conquer

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 Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →