Reverse Bits — 32-Bit Reversal With Shift Tricks and Mask Magic

Problem Statement#

Reverse bits of a given 32-bit unsigned integer. 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.

Constraints:

• The input must be a binary string of length 32.

Example 1:

Input:  n = 00000010100101000001111010011100
Output:    00111001011110000010100101000000 (= 964176192)

Example 2:

Input:  n = 11111111111111111111111111111101
Output:    10111111111111111111111111111111 (= 3221225471)

Example 3:

Input:  n = 1
Output:    10000000000000000000000000000000 (= 2147483648)

Why This Problem Matters#

Bit reversal underpins real-world systems: the Cooley–Tukey Fast Fourier Transform rearranges input by bit-reversed indices, network protocols sometimes serialize MSB-first while CPUs store LSB-first, and CRC and checksum hardware shifts data through bit-reversed registers. Even cryptographic primitives like Keccak (SHA-3) use bit-level rearrangements.

In interviews, Reverse Bits separates candidates who think procedurally from those who think in parallel bit operations. The naive shift loop works, but the divide-and-conquer "mask swap" technique — used in real production hot paths like LLVM's intrinsics — is what marks a candidate as bit-fluent. Apple, Microsoft, and Amazon use this question as a fast filter for systems-oriented roles.

The Core Insight#

Approach 1 — Shift and OR. Process one bit at a time. Shift the result left to make room, then OR in the lowest bit of the input. Shift the input right to expose the next bit. Repeat 32 times.

Approach 2 — Divide-and-conquer mask swap (parallel reversal in O(log 32) steps).

Reversing 32 bits decomposes recursively:

1. Swap adjacent pairs of bits (1-bit halves).
2. Swap adjacent pairs of 2-bit chunks.
3. Swap adjacent 4-bit nibbles.
4. Swap adjacent bytes.
5. Swap the two 16-bit halves.

After five mask-and-shift operations, the bits are fully reversed:

n = ((n & 0xAAAAAAAA) >> 1)  | ((n & 0x55555555) << 1)
n = ((n & 0xCCCCCCCC) >> 2)  | ((n & 0x33333333) << 2)
n = ((n & 0xF0F0F0F0) >> 4)  | ((n & 0x0F0F0F0F) << 4)
n = ((n & 0xFF00FF00) >> 8)  | ((n & 0x00FF00FF) << 8)
n = (n >> 16) | (n << 16)

This runs in constant five operations versus 32 iterations — over 6x faster in practice.

Visual Dry Run#

Input: n = 0b00000010100101000001111010011100

Approach 1 (shift loop) — first three iterations:

| iter | n (last bit) | result before | result << 1 \| n&1 | n >> 1 | |------|--------------|---------------|---------------------|--------| | 0 | 0 | 0 | 0 | 0...010 | | 1 | 0 | 0 | 0 | 0...001 | | 2 | 1 | 0 | 1 | 0...000 |

After 32 iterations, every input bit at position i ends up at position 31 - i of the result.

Approach 2 (mask swap) — step-by-step:

Start :  0000 0010 1001 0100 0001 1110 1001 1100
 
Step 1 (swap pairs of 1 bit):
         0000 0001 0110 1000 0010 1101 0110 1100
 
Step 2 (swap pairs of 2 bits):
         0000 0100 1010 0010 1110 0011 1010 0011
... (continues for 4-bit, 8-bit, 16-bit swaps)
 
Final :  0011 1001 0111 1000 0010 1001 0100 0000

Both approaches yield the same answer 964176192.

Solution (Optimal)#

Python#

class Solution:
    def reverseBits(self, n: int) -> int:
        # Approach 1: classic shift-and-OR loop (one bit per iteration)
        result = 0
        for _ in range(32):
            # shift result left to make room, append the lowest bit of n
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
 
class SolutionFast:
    def reverseBits(self, n: int) -> int:
        # Approach 2: divide-and-conquer mask reversal (5 ops)
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
        n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF   # mask to 32 bits in Python
        return n

JavaScript#

var reverseBits = function(n) {
    // Shift-and-OR loop. Use >>> 0 at the end to coerce to unsigned 32-bit.
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;   // logical right shift to handle the high bit cleanly
    }
    return result >>> 0;   // ensure non-negative 32-bit representation
};

Complexity: Time O(1) (32 fixed iterations or 5 fixed mask ops), Space O(1).

Common Mistakes#

1. Using arithmetic right shift on signed integers. In Java and JavaScript, >> performs sign extension. For unsigned bit reversal you need >>> (logical right shift). Otherwise the sign bit replicates and the loop misbehaves.

2. Forgetting to mask to 32 bits in Python. Python's integers are arbitrary precision. After the final shift in the divide-and-conquer approach, you must AND with 0xFFFFFFFF to confine the result to 32 bits.

3. Off-by-one shift count. Some candidates loop 31 times instead of 32, dropping the lowest bit. Always do exactly word_size iterations.

4. Missing the unsigned conversion at the end in JavaScript. Without result >>> 0, JavaScript's bitwise ops keep the value as a signed 32-bit int, which can show as negative when displayed.

5. Confusing bit reversal with byte reversal. Byte reversal (endian swap) reverses 8-bit chunks but preserves bit order within each byte. True bit reversal flips every bit position.

Interview Tips#

• Walk through the shift-and-OR loop on a 4-bit example before generalizing to 32 bits. Visual clarity reassures interviewers.
• After delivering Approach 1, mention "There is also a constant-time mask reversal that runs in 5 operations." If they ask for it, demonstrate the divide-and-conquer pattern. This separates a strong candidate from an exceptional one.
• If asked about caching repeated calls, mention the byte lookup table: precompute reversal of all 256 byte values, then assemble the 32-bit result from 4 lookups.
• For embedded or DSP roles, mention bit-reversal addressing in FFT and how some DSP processors have a dedicated bit-reverse instruction.

Follow-up Questions#

Q: How would you reverse a 64-bit integer? Add a sixth swap step for the 32-bit halves and extend each mask to 64 bits.

Q: How would you precompute and cache for batch processing? Build a 256-entry byte lookup table mapping each byte to its reversed form; reverse a 32-bit word in 4 lookups and bit shifts.

Q: Why does the divide-and-conquer approach use exactly five steps? Because log2(32) = 5. Each step doubles the chunk size that gets reversed, so you halve the problem 5 times.

Q: Can you avoid the loop entirely with built-ins? Java provides Integer.reverse(int) which compiles to a hardware instruction on many CPUs. C/C++ can use __builtin_bitreverse32 on Clang.

Key Takeaways#

• The shift-and-OR loop reverses 32 bits by extracting the lowest bit each iteration and prepending it to the result.
• The divide-and-conquer mask approach reverses bits in five constant-time operations using paired masks like 0x55555555.
• Logical right shift (unsigned) is essential — never use arithmetic right shift on signed integers when reversing bits.
• Mask the final value to 32 bits in arbitrary-precision languages like Python.
• Bit reversal underlies FFT addressing, CRC computation, and protocol-level bit ordering in real systems.
• Production hot paths often use precomputed byte tables or hardware bit-reverse instructions for maximum throughput.