245. Reverse 32 Bits

Why this mechanism works

Read the source from its least significant end and append each bit to a growing output by shifting the output left. After k steps, the low k bits of the original source have been read in reverse order. Completing all 32 steps moves the first-read bit into its required most significant position.

State and boundaries

After k iterations, answer is the reversal of the original low k bits within k positions; n has discarded those k bits by right shifts.

Protocol

1. Initialize answer to zero.
2. Repeat exactly 32 times.
3. Shift answer left and append n&1.
4. Shift n right.
5. Return answer.

Visualization

32-bit source 000...0001
first bit read is 1; then 31 zeros
output 1000...0000 = 2147483648

Python implementation

def reverse_32_bits(n):
    answer = 0
    for _ in range(32):
        answer = (answer << 1) | (n & 1)
        n >>= 1
    return answer

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 reverse_32_bits: answer = 0
n=1; answer=0

L3 reverse_32_bits: for _ in range(32):
n=1; answer=0; _=0

L4 reverse_32_bits: answer = (answer << 1) | (n & 1)
n=1; answer=1; _=0

L5 reverse_32_bits: n >>= 1
n=0; answer=1; _=0

L3 reverse_32_bits: for _ in range(32):
n=0; answer=1; _=1

L4 reverse_32_bits: answer = (answer << 1) | (n & 1)
n=0; answer=2; _=1

L3 reverse_32_bits: for _ in range(32):
n=0; answer=2; _=2

L4 reverse_32_bits: answer = (answer << 1) | (n & 1)
n=0; answer=4; _=2

... 54 intermediate state changes omitted ...

L3 reverse_32_bits: for _ in range(32):
n=0; answer=536870912; _=30

L4 reverse_32_bits: answer = (answer << 1) | (n & 1)
n=0; answer=1073741824; _=30

L3 reverse_32_bits: for _ in range(32):
n=0; answer=1073741824; _=31

L4 reverse_32_bits: answer = (answer << 1) | (n & 1)
n=0; answer=2147483648; _=31

L2 reverse_32_bits: answer = 0
n=0; answer=0

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=0

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=1

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=2

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=3

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=4

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=5

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=6

... 21 intermediate state changes omitted ...

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=28

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=29

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=30

L3 reverse_32_bits: for _ in range(32):
n=0; answer=0; _=31

Why the solution is correct

Each update appends the next source bit to the reversed processed prefix, preserving the k-bit invariant. After 32 iterations all source positions, including leading zeros, have been consumed; original bit i occupies output position 31-i.

Time and space

O(32)=O(1) time and O(1) storage under the fixed-width contract. Generalizing to width w uses O(w) bit-processing iterations.

Common mistakes

Looping only while n is nonzero loses leading-zero positions. Reversing a decimal string does not reverse the fixed-width binary representation.

Reasoning card

Transfer exercise

Reverse twice and prove the original 32-bit value is restored; use that property for randomized verification.