Reverse Bits

Problem

Given a 32-bit unsigned integer n, reverse the order of its bits and return the result as an unsigned integer. The bit at position i (counting from the least-significant end, 0..31) must end up at position 31 - i.

Examples

• 43261596 (00000010100101000001111010011100) → 964176192 (00111001011110000010100101000000) — the two 32-bit strings are mirror images.
• 4294967293 (11111111111111111111111111111101) → 3221225471 (10111111111111111111111111111111) — the single 0 moves from position 1 to position 30.
• 1 (00...001) → 2147483648 (10...000) — the lone set bit moves from position 0 to position 31.

Constraints

• The input is a 32-bit unsigned integer.

Follow-up: if the function is called many times, can you avoid redoing full work each time (caching, or a fixed-step approach)?

Think about it first

TL;DR

Read the low bit and push it onto a left-shifting accumulator, 32 times: O(1) time (fixed 32 steps), O(1) space. Or use a 5-step masked half-swap.

Approach 1 — Brute force: build the result bit by bit

Repeatedly take the lowest bit of n and append it to a result that shifts left each round. The first bit read (position 0) gets shifted left 31 more times, landing at position 31, exactly the mirror.

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)   # make room, drop in low bit
        n >>= 1                             # expose the next bit
    return result

Walkthrough (shown on an 8-bit analogy, reversing 00000011 → 11000000):

The two set bits read first get shifted all the way to the top. On the real problem the loop runs 32 times.

Complexity: O(1) time (a fixed 32 iterations regardless of input), O(1) space. The follow-up asks about repeated calls; the mask approach below answers it with a fixed five steps.

Approach 2 — Divide and conquer with masks

Reversing a bit string equals swapping its two halves, then reversing within each half. Reversing within a half is itself swap-the-halves recursively, down to single bits. Every swap at a given level runs in parallel with one mask pair: shift the bits that must move right, shift the bits that must move left, and OR them. Do adjacent single bits, then 2-bit groups, then 4-bit nibbles, then bytes, then the two 16-bit halves: log2(32) = 5 steps, no loop.

flowchart LR
    A[input word] --> B[swap adjacent bits]
    B --> C[swap 2-bit groups]
    C --> D[swap nibbles]
    D --> E[swap bytes]
    E --> F[swap 16-bit halves]
    F --> G[reversed word]

The mask pairs pick out alternating groups: 0xAAAAAAAA is 1010... (the odd positions), 0x55555555 is 0101... (the even positions), and so on for wider groups.

def reverseBits(n: int) -> int:
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)   # swap adjacent bits
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)   # swap 2-bit groups
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)   # swap nibbles
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)   # swap bytes
    n = (n >> 16) | (n << 16)                               # swap 16-bit halves
    return n & 0xFFFFFFFF                                   # keep it 32-bit

Walkthrough (adjacent-swap step on ...1101): 0xAAAAAAAA masks the odd-position bits and shifts them down one, 0x55555555 masks the even-position bits and shifts them up one, so each neighbouring pair trades places. After all five steps the whole 32-bit word is mirrored. The final & 0xFFFFFFFF matters in Python, where << does not wrap around and would otherwise leave stray high bits set.

Complexity: O(1) time (exactly five steps), O(1) space — the standard answer to the “many calls” follow-up.

Common pitfalls

• Wrong iteration count: you must loop exactly 32 times, not “until n == 0,” or leading zeros in the input are never shifted into place and the result is too small.
• Shift order: it’s result = (result << 1) | (n & 1) — shift result first, then OR in the new bit; ORing before shifting corrupts the low bit.
• Python has no fixed width: << grows numbers without wrapping, so mask with & 0xFFFFFFFF at the end of the mask approach (Approach 1 stays bounded on its own).
• Mask typos: the 0xAAAA/0x5555 style pairs are complementary; a mismatched pair drops or duplicates bits. Double-check each level covers all 32 bits.

Pattern takeaway

Two reusable ideas: (1) to reverse or reorder bits, read from one end and accumulate onto the other with shift-and-OR; (2) whole-word operations parallelize across bits — a divide-and-conquer “swap halves at every scale” collapses an O(width) loop into O(log width) masked steps. That mask-and-swap template also reverses bytes, computes popcounts, and more.