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 a 5-step masked half-swap.

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

The naive intuition: 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.

class Solution:
    def reverseBits(self, 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 hint (“build bit by bit”) is really about the mask trick below, which uses a fixed five steps.

Approach 2 — Divide and conquer with masks

The insight: reversing a bit string equals swapping its two halves, then reversing within each half — and reversing within halves is itself swap-the-halves recursively, down to single bits. You can do every swap at one level in parallel with a mask: 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.

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.

class Solution:
    def reverseBits(self, 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.

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.