Reverse Bits — Solution

Problem

Given a 32-bit unsigned integer, return the integer whose binary representation is the bit-for-bit mirror of the input's binary representation — the least significant bit becomes the most significant bit, and so on.

• Input: n = 43261596 (binary: 00000010100101000001111010011100)
• Output: 964176192 (binary: 00111001011110000010100101000000)
• Explanation: Reading all 32 binary digits of the input from right to left produces the output.

A second example where a single 0 bit near the end shifts all the way to the front:

• Input: n = 4294967293 (binary: 11111111111111111111111111111101)
• Output: 3221225471 (binary: 10111111111111111111111111111111)
• Explanation: Only bit 1 (the second-from-last) was 0; after reversal it lands at bit 30 (the second-from-first).

Intuition

We need each bit at position i to move to position 31 - i. The simplest way to see this: if we repeatedly peel off the rightmost bit of the input and attach it to the right of an accumulator while shifting the accumulator left, after 32 rounds the original bit 0 ends up at bit 31 and the original bit 31 ends up at bit 0. A faster alternative does the same redistribution in parallel by swapping bits in progressively larger groups — adjacent singles, then pairs, nibbles, bytes, and finally 16-bit halves — using just five masked shift-and-OR operations.

Approach 1 — Bit-by-Bit Loop

Peel the LSB off n and place it on the right of result, then shift both registers one position. After 32 rounds the bits are fully reversed.

1. Initialize result = 0.
2. Repeat 32 times:
   • Shift result left by 1.
   • OR the current LSB of n into result.
   • Shift n right by 1 (unsigned — no sign extension).
3. Return result.

1def reverseBits(n: int) -> int:
2    result = 0
3    for _ in range(32):
4        result = (result << 1) | (n & 1)  # append LSB of n onto the growing result
5        n >>= 1
6    return result

Time: O(1) — exactly 32 iterations regardless of input value.
Space: O(1) — two integer registers, no auxiliary data structures.

Approach 2 — Divide and Conquer (Parallel Bit Swapping)

Swap bits in progressively larger groups using complementary bitmask pairs. Each of the five steps runs in constant time and handles all 32 bits at once.

1. Swap adjacent single bits using mask 0x55555555 (...01010101).
2. Swap adjacent bit-pairs using mask 0x33333333 (...00110011).
3. Swap adjacent nibbles using mask 0x0F0F0F0F (...00001111).
4. Swap adjacent bytes using mask 0x00FF00FF.
5. Swap the two 16-bit halves.

1def reverseBits(n: int) -> int:
2    n = ((n & 0xAAAAAAAA) >> 1)  | ((n & 0x55555555) << 1)   # swap adjacent bits
3    n = ((n & 0xCCCCCCCC) >> 2)  | ((n & 0x33333333) << 2)   # swap adjacent pairs
4    n = ((n & 0xF0F0F0F0) >> 4)  | ((n & 0x0F0F0F0F) << 4)   # swap nibbles
5    n = ((n & 0xFF00FF00) >> 8)  | ((n & 0x00FF00FF) << 8)   # swap bytes
6    n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF                  # swap halves; mask to 32 bits
7    return n

Time: O(1) — five fixed passes; this approach generalizes to O(log n) passes for an n-bit integer.
Space: O(1) — all operations are in-place on the integer itself.

Complexity Summary

Common Mistakes

• Java signed right shift (>> instead of >>>) — n >> 1 on a negative int fills the vacated high bit with the sign bit, corrupting every subsequent iteration; always use >>> in Java for this problem.
• Iterating 31 times instead of 32 — a loop that runs i < 31 stops one step early, which drops the most significant bit of the input (it should become the least significant bit of the result).
• Skipping the & 0xFFFFFFFF mask in Python's D&C approach — Python integers have arbitrary precision, so the final half-word swap (n << 16) can produce a value wider than 32 bits; the explicit mask is required to trim it.
• Swapping the D&C masks — in the adjacent-pairs step the "upper" bits use mask 0xCCCC... (binary 1100 repeating) and the "lower" bits use 0x3333... (binary 0011 repeating); mixing them up silently computes the wrong swap, producing a result that passes most test cases but fails others.
• Using signed right shift for the "upper" mask in D&C — in Java, (n & 0xAAAAAAAA) >> 1 performs an arithmetic shift on a value whose MSB could be 1 (if bit 31 was set), introducing a spurious 1-bit at position 30; use >>> consistently in Java's D&C version.

Related Problems

• number-of-1-bits — uses the same n & 1 + right-shift loop, but accumulates a count instead of reversing
• counting-bits — extends single-bit extraction across a range using the same masking primitives
• single-number — foundational XOR-based bit manipulation; shows how bit operations replace arithmetic
• bitwise-and-of-numbers-range — bit-masking over a range, reinforcing how masks isolate and preserve groups of bits
• missing-number — XOR trick that demonstrates how reversible bit operations can find hidden values in integer arrays