Problem Description

You are given a 32-bit signed integer n. Your task is to reverse all the bits in this integer and return the resulting value.

When reversing bits, the bit at position 0 (rightmost/least significant bit) should move to position 31 (leftmost/most significant bit), the bit at position 1 should move to position 30, and so on. Each bit maintains its value (0 or 1) but changes its position to create a mirror image of the original bit pattern.

For example, if you have the binary representation 00000010100101000001111010011100, after reversing the bits, you would get 00111001011110000010100101000000.

The solution works by iterating through all 32 bits of the input number. For each iteration i:

• Extract the least significant bit of n using (n & 1)
• Place this bit at position (31 - i) in the result using left shift: (n & 1) << (31 - i)
• Combine it with the result using the OR operation: ans |= (n & 1) << (31 - i)
• Right shift n by 1 to process the next bit: n >>= 1

This process continues for all 32 bits, effectively reversing the entire bit sequence of the input integer.

Intuition

To reverse the bits of a number, we need to swap the positions of bits symmetrically around the center. The bit at position 0 should go to position 31, the bit at position 1 should go to position 30, and so on.

Think of it like reversing a string - you would take characters from one end and place them at the opposite end. Similarly, with bits, we need to take each bit from its current position and place it at its mirror position.

The key insight is that we can process the bits one by one from right to left (least significant to most significant). As we examine each bit:

1. We need to extract it from its current position
2. We need to place it at its new reversed position

To extract the rightmost bit, we use n & 1, which gives us the value (0 or 1) of the least significant bit.

To place this bit at its reversed position, we need to shift it left. If we're processing the i-th bit (counting from 0), its reversed position would be 31 - i. So we shift the extracted bit left by 31 - i positions using << (31 - i).

After processing each bit, we shift n right by 1 position (n >>= 1) to bring the next bit into the least significant position for processing in the next iteration.

By accumulating all these repositioned bits using the OR operation (|=), we build up the reversed number bit by bit. After 32 iterations, we've processed all bits and have our complete reversed result.

This approach is efficient because it processes each bit exactly once and uses simple bitwise operations that are very fast at the hardware level.

Solution Approach

The solution uses bit manipulation to reverse the bits of a 32-bit integer. Let's walk through the implementation step by step:

Algorithm Overview: We iterate through all 32 bits of the input number, extracting each bit from the right side and placing it at the corresponding position on the left side of our result.

Step-by-step Implementation:

1. Initialize the result variable: Start with ans = 0, which will store our reversed bit pattern.

2. Loop through 32 bits: Use a for loop with i ranging from 0 to 31 to process each bit position.

3. Extract and reposition each bit: For each iteration i:

   • Extract the rightmost bit of n using n & 1. This AND operation with 1 gives us the value of the least significant bit (either 0 or 1).
   • Calculate the reversed position as 31 - i. When i = 0, the bit goes to position 31; when i = 31, the bit goes to position 0.
   • Shift the extracted bit to its new position using (n & 1) << (31 - i).
   • Combine this bit with our result using the OR operation: ans |= (n & 1) << (31 - i).

4. Prepare for next bit: After processing the current bit, right shift n by 1 position (n >>= 1) to bring the next bit into the least significant position for the next iteration.

Example Walkthrough: Let's say n = 5 (binary: 00000000000000000000000000000101)

• Iteration 0: Extract bit 1, place at position 31 → ans = 10000000000000000000000000000000
• Iteration 1: Extract bit 0, place at position 30 → ans = 10000000000000000000000000000000
• Iteration 2: Extract bit 1, place at position 29 → ans = 10100000000000000000000000000000
• Continue for remaining 29 iterations...

After all 32 iterations, we return ans which contains the reversed bit pattern.

Time Complexity: O(1) - We always iterate exactly 32 times regardless of input. Space Complexity: O(1) - We only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example with n = 11 (in decimal).

Initial Setup:

• Input: n = 11
• Binary: 00000000000000000000000000001011
• Result: ans = 0

Key Iterations:

Iteration 0 (i=0):

• Current n: ...001011
• Extract rightmost bit: n & 1 = 1
• Place at position 31: 1 << 31
• Update result: ans = 10000000000000000000000000000000
• Shift n right: n = ...000101

Iteration 1 (i=1):

• Current n: ...000101
• Extract rightmost bit: n & 1 = 1
• Place at position 30: 1 << 30
• Update result: ans = 11000000000000000000000000000000
• Shift n right: n = ...000010

Iteration 2 (i=2):

• Current n: ...000010
• Extract rightmost bit: n & 1 = 0
• Place at position 29: 0 << 29
• Result unchanged: ans = 11000000000000000000000000000000
• Shift n right: n = ...000001

Iteration 3 (i=3):

• Current n: ...000001
• Extract rightmost bit: n & 1 = 1
• Place at position 28: 1 << 28
• Update result: ans = 11010000000000000000000000000000
• Shift n right: n = ...000000

Iterations 4-31:

• Since n = 0 after iteration 3, all remaining bits are 0
• n & 1 = 0 for all remaining iterations
• The result remains: ans = 11010000000000000000000000000000

Final Result:

• Binary: 11010000000000000000000000000000
• Decimal: 3489660928

The original bits 1011 from the rightmost positions have been moved to the leftmost positions as 1101, effectively reversing the bit pattern across the entire 32-bit integer.

Solution Implementation

Time and Space Complexity

The time complexity is O(1), not O(log n) as stated in the reference answer. This is because the loop always runs exactly 32 iterations regardless of the input value n. Even though we're processing a 32-bit integer, the number of operations is constant and doesn't scale with the magnitude of n.

The space complexity is O(1), which matches the reference answer. The algorithm only uses a fixed amount of extra space for the variable ans and the loop counter i, regardless of the input size.

The reference answer appears to be incorrect regarding time complexity. For this specific problem of reversing bits in a 32-bit integer, the time complexity should be O(1) since we always perform exactly 32 iterations. If this were a more general bit reversal problem where the number of bits varied with n, then O(log n) would be appropriate since the number of bits in n is proportional to log n.

Common Pitfalls

1. Early Termination When n Becomes 0

A common mistake is to optimize by breaking the loop early when n becomes 0, thinking all remaining bits are 0:

# INCORRECT approach
def reverseBits(self, n: int) -> int:
    result = 0
    for i in range(32):
        if n == 0:  # Wrong! This causes incorrect results
            break
        result |= (n & 1) << (31 - i)
        n >>= 1
    return result

Why this fails: Even if n becomes 0 during iteration, we still need to continue placing zeros in the remaining positions. Breaking early leaves those positions unprocessed, resulting in incorrect bit placement.

Example: For n = 1 (binary: 00000000000000000000000000000001), the correct reversal is 10000000000000000000000000000000 (2147483648). But breaking early after the first iteration would incorrectly return 2147483648 without properly handling the remaining bit positions.

2. Using Wrong Shift Direction or Amount

Another pitfall is confusing the shift operations:

# INCORRECT approaches
result |= (n & 1) << i  # Wrong: shifts to wrong position
result |= (n & 1) >> (31 - i)  # Wrong: uses right shift instead of left
result |= (n >> 1) << (31 - i)  # Wrong: extracts wrong bit

Solution: Always remember:

• Use n & 1 to extract the rightmost bit
• Use << (31 - i) to place it at the reversed position
• Use n >>= 1 to move to the next bit

3. Incorrect Bit Position Calculation

Some might incorrectly calculate the reversed position:

# INCORRECT
result |= (n & 1) << (32 - i)  # Wrong: shifts by 32 to 1 instead of 31 to 0
result |= (n & 1) << (30 - i)  # Wrong: incorrect range

Solution: The correct formula is 31 - i because:

• Bit positions range from 0 to 31 (total 32 positions)
• When i = 0, we want position 31
• When i = 31, we want position 0

4. Not Processing All 32 Bits

Processing fewer than 32 bits leads to incomplete reversal:

# INCORRECT
for i in range(16):  # Wrong: only processes half the bits
    result |= (n & 1) << (31 - i)
    n >>= 1

Solution: Always iterate exactly 32 times to ensure all bits are properly reversed, regardless of the input value.