Reverse Bits

Problem

Given a 32-bit unsigned integer n, return the unsigned integer obtained by writing the 32 bits of n in reverse order, so bit 0 becomes bit 31, bit 1 becomes bit 30, and so on.

• 0 <= n <= 2^32 - 1
• The result must also be interpreted as unsigned 32 bits: reversing 1 gives 2^31, not a negative number.
• Leading zeros are significant: the value is always treated as exactly 32 bits wide.

Examples

• n = 305419896 (00010010001101000101011001111000) → 510274632 (00011110011010100010110001001000).
• n = 1 → 2147483648: the single set bit moves from position 0 to position 31.
• n = 4294967295 (all ones) → 4294967295; reversing a symmetric pattern changes nothing.

Hints

1. Build the result one bit at a time: shift the result left, then append the lowest bit of n, then shift n right.
2. Do you really need to loop 32 times? Think about swapping halves, then quarters, then...
3. Divide and conquer with masks: swap the two 16-bit halves, then swap adjacent 8-bit chunks within each half, then 4-bit, 2-bit, 1-bit. Five constant-time steps.