Code Implementation

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
      

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; ++i) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
};
      

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}
      

var reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n = n >>> 1;
    }
    return result >>> 0;
};
      

Problem Description

The Reverse Bits problem asks you to reverse the bits of a given 32-bit unsigned integer. That is, you are given an integer n, and you must return an integer whose binary representation is the reverse of the binary representation of n.

For example, if the input n is 00000010100101000001111010011100 (in binary), your function should return 00111001011110000010100101000000.

• Input: A single 32-bit unsigned integer n
• Output: A single 32-bit unsigned integer representing the reversed bits of n
• All 32 bits are considered, including leading zeros

Thought Process

The first idea that comes to mind is to somehow "flip" or "mirror" the bits of the number. Since integers are stored as binary, we need to process each of the 32 bits individually and build a new number with the bits in reverse order.

A brute-force approach would be to extract each bit from the input, then set the corresponding bit in the output at the mirrored position. However, we can optimize this by building the output bit by bit, shifting left and adding the next extracted bit from the input.

The main challenge is handling the bit manipulations correctly, making sure all 32 bits are processed (even if they are zeros).

Solution Approach

Let's break down the steps to reverse the bits of a 32-bit unsigned integer:

1. Initialize a result variable: Start with result = 0. This will hold the reversed bits as we build them.
2. Iterate over all 32 bits: Use a loop that runs 32 times, once for each bit.
3. Extract the least significant bit (LSB) from n: Use n & 1 to get the rightmost bit.
4. Append the extracted bit to result: Shift result left by 1 (to make room), then use bitwise OR to add the extracted bit.
5. Shift n right by 1: This discards the bit we just processed, preparing for the next bit.
6. Repeat: Continue this for all 32 bits.
7. Return the result: After the loop, result contains the reversed bits.

This approach uses bitwise operations because they are very fast and efficient for manipulating binary data.

Example Walkthrough

Let's walk through an example. Suppose the input n is 00000010100101000001111010011100 (which is 43261596 in decimal).

1. Initialize result = 0.
2. On each iteration:
   • Extract the rightmost bit of n (e.g., n & 1).
   • Shift result left by 1, then add the extracted bit.
   • Shift n right by 1 (discard the processed bit).
3. For the first few steps:
   • 1st iteration: n & 1 = 0, result = 0
   • 2nd iteration: n & 1 = 0, result = 0
   • 3rd iteration: n & 1 = 1, result = 1
   • ...continue for all 32 bits...
4. After 32 iterations, result becomes 00111001011110000010100101000000 (964176192 in decimal).

This process ensures that the leftmost bit of the input becomes the rightmost bit of the output, and so on.

Time and Space Complexity

Brute-force Approach: Even with brute-force (processing each bit one-by-one), we only need to loop 32 times, so the time complexity is O(1) (constant time, since 32 is a fixed number).

Optimized Approach: The described approach is already optimal, as it processes each bit exactly once. The time complexity remains O(1).

Space Complexity: We only use a constant amount of extra space (result and a few counters), so the space complexity is also O(1).

Summary

The Reverse Bits problem is a classic example of bit manipulation. By iteratively extracting the least significant bit and building the result from left to right, we can efficiently reverse all 32 bits of the input. The solution is both elegant and efficient, requiring only constant time and space, and demonstrates the power of bitwise operations for low-level data processing.