Reverse Bits

How it works

We are given a 32-bit unsigned integer and need to reverse its bits.

Instead of reversing bits one-by-one, we can do this much faster by using a classic bit-manipulation trick called bitwise divide and conquer.

The key idea is:

• Reverse bits in large blocks first
• Then gradually reverse smaller and smaller blocks
• Until all individual bits are reversed

This works because reversing bits is equivalent to:

• swapping the left half with the right half
• then swapping bytes
• then nibbles (4 bits)
• then pairs
• finally single bits

Each step rearranges bits closer to their final reversed positions.

Steps

1. Start with the original number n stored in res.
2. Swap the left 16 bits with the right 16 bits.
3. Swap bits in blocks of:
   • 8 bits (bytes)
   • 4 bits
   • 2 bits
   • 1 bit
4. After each step, use bit masks to isolate groups of bits and shift them to their new positions.
5. Ensure the final result stays within 32 bits.
6. Return the reversed number.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Using Signed Right Shift Instead of Unsigned

In languages like Java and JavaScript, using >> (signed right shift) instead of >>> (unsigned right shift) can cause incorrect results. The signed shift preserves the sign bit, which leads to unexpected behavior when the most significant bit is set. Always use unsigned right shift for bit reversal operations.

Hardcoding the Wrong Bit Width

The problem specifies a 32-bit unsigned integer, so all operations must process exactly 32 bits. A common mistake is iterating fewer than 32 times or not accounting for leading zeros. Every bit position matters in reversal, so the loop must always run for all 32 bits regardless of the input value.

class Solution:
    def reverseBits(self, n: int) -> int:
        res = n
        res = (res >> 16) | (res << 16) & 0xFFFFFFFF
        res = ((res & 0xff00ff00) >> 8) | ((res & 0x00ff00ff) << 8)
        res = ((res & 0xf0f0f0f0) >> 4) | ((res & 0x0f0f0f0f) << 4)
        res = ((res & 0xcccccccc) >> 2) | ((res & 0x33333333) << 2)
        res = ((res & 0xaaaaaaaa) >> 1) | ((res & 0x55555555) << 1)
        return res & 0xFFFFFFFF

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = n;
        ret = (ret >> 16) | (ret << 16);
        ret = ((ret & 0xff00ff00) >> 8) | ((ret & 0x00ff00ff) << 8);
        ret = ((ret & 0xf0f0f0f0) >> 4) | ((ret & 0x0f0f0f0f) << 4);
        ret = ((ret & 0xcccccccc) >> 2) | ((ret & 0x33333333) << 2);
        ret = ((ret & 0xaaaaaaaa) >> 1) | ((ret & 0x55555555) << 1);
        return ret;
    }
};