Reverse Bits

Reverse Bits

What is this problem about?

The Reverse Bits interview question asks you to reverse the bits of a given 32-bit unsigned integer and return the result as an unsigned integer. For example, if the binary representation of the input is 00000010100101000001111010011100, the reversed binary is 00111001011110000010100101000000, and you return the corresponding unsigned integer value.

Why is this asked in interviews?

This problem is asked at Apple, Microsoft, Qualcomm, Meta, Nvidia, Airbnb, Amazon, and Google because bit manipulation is fundamental to low-level programming, embedded systems, hardware description languages, and competitive programming. Understanding how to extract, shift, and accumulate bits demonstrates mastery of bitwise operations — skills directly applicable to network programming, compression, and cryptography.

Algorithmic pattern used

Two main patterns: linear bit-by-bit reversal and divide-and-conquer reversal. For the simple approach: iterate 32 times, extract the least significant bit of n with n & 1, add it to the result (shifting result left), then shift n right. For the divide-and-conquer approach (useful for repeated calls): swap adjacent bits, then adjacent 2-bit groups, then 4-bit groups, up to 16-bit halves — this reverses bits in O(log W) mask operations and is O(1) for fixed 32-bit integers.

Example explanation

Input: n = 43261596 (binary: 00000010100101000001111010011100)

Simple reversal:

• Extract LSB of n, place as MSB of result.
• Repeat 32 times, shifting n right and result left each time.

Result: 964176192 (binary: 00111001011110000010100101000000).

Divide-and-conquer: Swap 16-bit halves, then 8-bit chunks, then 4-bit nibbles, etc.

Common mistakes candidates make

• Using signed right shift (arithmetic) instead of unsigned right shift — in Python, use n >> 1 but mask to 32 bits with n &= 0xFFFFFFFF.
• Not initializing the result to 0 before accumulating bits.
• Iterating fewer than 32 times — all 32 positions must be processed even if the input has leading zeros.
• Forgetting that Python integers are arbitrary-precision — always mask to 32 bits for correctness.

Interview preparation tip

For the Reverse Bits coding problem, the bit manipulation and divide-and-conquer interview pattern is the optimal approach for repeated calls. Know both the simple iterative approach (O(32)) and the mask-based swap approach. Interviewers at Qualcomm and Nvidia — hardware-oriented companies — often ask for the divide-and-conquer version and its scalability to 64-bit integers. Practice both implementations and know when each is appropriate.