Comment by FabHK

Also, typing it out while you run the algo in your head: 42 even -> 0, 21 odd -> 1, 10 even -> 0, 5 odd -> 1, 2 even -> 0, 1 odd -> 1.