Reverse Bits - Video Solutions

Problem Overview: You are given a 32-bit unsigned integer and must reverse its binary representation. The least significant bit becomes the most significant bit, the second least becomes the second most, and so on. The result is another 32-bit integer formed from this reversed bit order.

Approach 1: Bitwise Shift and OR (Time: O(32), Space: O(1))

This method builds the reversed number one bit at a time. Iterate through all 32 bits of the input integer. At each step, extract the last bit using n & 1, shift the result left by one position, and append the extracted bit using a bitwise OR. Then shift the original number right using n >> 1. After 32 iterations, the constructed number contains the reversed bit order. This approach relies purely on basic bit manipulation operations and is easy to implement in any language.

The key idea is treating the integer as a stream of bits. Each iteration pulls the least significant bit and pushes it into the reversed result from the left side. Because a 32-bit integer always has a fixed width, the loop runs exactly 32 times, making the algorithm effectively constant time. This is the most common solution used in interviews and coding platforms.

Approach 2: Bit Manipulation with Precomputed Masks (Time: O(1), Space: O(1))

This approach reverses bits in groups instead of processing them one by one. It uses precomputed bit masks to swap halves, then quarters, then smaller groups of bits. For example, swap the left and right 16-bit halves, then swap 8-bit groups, then 4-bit groups, and continue until single bits are swapped. Each stage uses masks and shifts such as (n & mask) << k and (n >> k) & mask to reposition groups of bits.

The idea follows a divide and conquer pattern. Instead of reversing sequentially, the algorithm repeatedly splits the integer into smaller segments and swaps them using bit masks. Because the number of operations is fixed and independent of input value, the complexity is constant time. This technique appears frequently in systems programming and performance-critical bit operations.

Recommended for interviews: The shift-and-OR approach is what most interviewers expect. It demonstrates clear understanding of bit manipulation fundamentals such as masking, shifting, and constructing integers bit by bit. The mask-based divide-and-conquer technique is more advanced and useful when discussing optimized bit tricks or low-level performance.