Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Shift exactly thirty-two positions: The Bit Mirror.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Reverse bits matches the clues
- 2Keep this true after every move: after k rounds, result contains the reversed lowest k input bits
- 3Reach the result within O(32) time and O(1) space
Rules and pressure
- Target cost: O(32) time and O(1) space
- State rule: after k rounds, result contains the reversed lowest k input bits
Lesson 1 of 3
Live algorithm trace
Reverse bits
Complete execution1 of 5
Start before transferring any of the 32 bits.
1
result = 02
repeat 32 times3
result = (result << 1) | (value & 1)4
value unsigned-shifts right5
return result as unsignedinputTail = 11100result = 0
Truth to preserve / Cost target
Truth to preserve
after k rounds, result contains the reversed lowest k input bits
Cost target
O(32) time and O(1) space
Read the input's lowest bit, append it to the result's right edge, then shift the input. Exactly 32 rounds preserve leading zeros as trailing zeros.
Your call · What should guide every step of this algorithm?