Reverse Bits

Reverse the bits of a 32-bit unsigned integer. A naive string conversion is unnecessary; use bit operations instead.

Function signature

func ReverseBits(n uint32) uint32

Inputs / outputs

• n: 32-bit unsigned integer.
• Return: n with bits reversed.

Example

Input:  00000010100101000001111010011100
Output: 00111001011110000010100101000000

Constraints

• Input fits in 32 bits.

Core idea (near-solution)

Iteratively shift bits from n into the result.

Invariant: after k iterations, the result contains the reversed top k bits of the original number.

Algorithm (step-by-step)

1. Initialize res = 0.
2. Repeat 32 times:
   • res = (res << 1) | (n & 1).
   • n >>= 1.
3. Return res.

Correctness sketch

• Invariant: after k iterations, the result contains the reversed top k bits of the original number.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

Trace (hand walkthrough)

Example input:
Input:  00000010100101000001111010011100
Output: 00111001011110000010100101000000

Walk:
- process LSBs of input ...1100 -> res builds ...0011
- after 32 steps, bits are reversed -> 00111001011110000010100101000000

Pitfalls to avoid

• Looping until n==0 (must always do 32 steps).
• Using signed shifts.

Complexity

• Time: O(1) (32 iterations).
• Extra space: O(1).

Implementation notes (Go)

• Use uint32 throughout to avoid sign extension.