Converting a number from N to 0 in binary
I think you can just do a simple breadth-first-search on this. First note that:


There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop.
It doesn't make sense to do move #2 twice in a row.


The important thing to do while searching is to note whether the number we've arrived at was by doing move #2 (otherwise we'd get stuck in a loop). So here's a pseudocode:


Put the current number into a queue with flag 0
While the dequeued number is not zero:


If you can do move #1 on the dequeued number then do move #1 and put that in a queue with flag 0
If the dequeued number's flag is 0, then do move #2, and put that in the queue with flag 1