Reverse Bits

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

Why this is worth learning

Fixed width is the point. Reversing only the significant binary digits of 1 would return 1, but reversing all 32 positions places that bit at position 31.

Before coding: one-minute experiment

What is ReverseBits(1), and why is ReverseBits(ReverseBits(x)) equal to x?

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)

Writing a 32-character binary string and reversing it gives a simple correct model. Now remove the temporary string: read one low bit at a time from the input and append it to a growing result using a shift. There are always 32 positions to process. A loop that stops when the remaining value reaches zero implements a different significant-digit reversal and fails even for input 1.

Iteratively shift bits from n into the result.

Invariant: after k iterations, the low k positions of res hold the reverse of the original k least-significant bits, and n is the original input shifted right by k. The remaining 32-k iterations still process positions whose bit value may be zero.

Algorithm (step-by-step)

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

Correctness sketch

After k iterations, the result holds the reverse of the original k least-significant bits, and the shifted input contains the remaining original bits. Shifting result left makes space for the next bit; OR with n&1 appends it. Shifting n right discards exactly the consumed bit. After 32 steps every original position has moved to its mirrored position, including leading zero positions. The uint32 types enforce logical shifts and exactly the requested width.

Trace (hand walkthrough)

For n=13, display only enough low positions to see the first four steps. The actual register remains 32 bits wide.

Iterations completed	Remaining n	res	Consumed bit
0	1101	0	none
1	110	1	1
2	11	10	0
3	1	101	1
4	0	1011	1
32	0	10110000000000000000000000000000	28 more zero positions

The result is 2952790016. Stopping after iteration 4 would return 11 and lose the fixed-width contract.

Pitfalls to avoid

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

Debugging lens

Test zero, all ones, every single-bit input, and alternating masks. A loop that stops when n becomes zero loses the fixed-width leading positions.

Complexity

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

Implementation notes (Go)

• Use uint32 throughout to avoid sign extension.

Reconstruction checkpoint

What is ReverseBits(1), and why is ReverseBits(ReverseBits(x)) equal to x?

Model answer

ReverseBits(1) is 2147483648 (1 shifted left 31 positions). Mirroring index i to 31-i twice returns it to i, so reversal is an involution over all 32-bit patterns.

Return to Bit Manipulation · Module quiz