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

More Math practice problems

See all Math problems →