Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Subtract the largest shifted divisor: The Binary Divider.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Integer division by doubling matches the clues
- 2Keep this true after every move: original dividend magnitude equals accumulated quotient times divisor plus remaining magnitude
- 3Reach the result within O(log squared dividend) simple doubling
Rules and pressure
- Target cost: O(log squared dividend) simple doubling
- State rule: original dividend magnitude equals accumulated quotient times divisor plus remaining magnitude
Lesson 1 of 3
Live algorithm trace
Integer division by doubling
Complete execution1 of 5
Separate sign and work with positive magnitudes.
1
record sign and use positive magnitudes2
while dividend >= divisor3
double divisor and multiple while they fit4
subtract largest fit5
add its multiple to quotient6
apply sign and clampdividend = 10divisor = 3sign = +
Truth to preserve / Cost target
Truth to preserve
original dividend magnitude equals accumulated quotient times divisor plus remaining magnitude
Cost target
O(log squared dividend) simple doubling
Build the quotient from powers of two. Repeatedly subtract the largest doubled divisor that fits, adding its matching quotient bit.
Your call · What should guide every step of this algorithm?