Reverse Bits

Given a 32-bit unsigned integer n, reverse the bits of the binary representation of n and return the result.

Reversing 00000000000000000000000000010101, which represents the unsigned integer 21, gives us 10101000000000000000000000000000 which represents the unsigned integer 2818572288.

Approach

Iterate through all 32 bits. At each step, shift the result left by one and add the least significant bit of n. Then shift n right.

Why It Works

Building the result bit-by-bit from least significant to most significant produces the exact reversed order. After 32 iterations, all bits are reversed.

Complexity

• Time: O(1) (32 steps)
• Space: O(1)

Reference Implementation (Python)

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