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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →