Traveling between integers- powers of 2 
Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. 

Consider the integers. We can only travel directly between two integers with a difference whose absolute value is a power of 2 and every time we do this it is called a step. The distance $d$ between two integers is the minimum number of steps required to get from one to the other. Note however that we can travel backwards. For instance $d(2,17)$ is 2: $2+16=18 \rightarrow 18-1=17$. 
How can we prove that for any integer n, we will always have some $d(a,b)=n$ where$b>a$? 

If we are only able to take forward steps I know that  the number of 1s in the binary representation of $b-a$ would be $d(a,b)$. However, we are able to take steps leftward on the number line...

Presumably you mean every natural number $n$, not every integer $n$. We can simplify things by taking $a=0$ without loss of generality and then writing $d(b):=d(0,b)$. Also, it's enough to show that for every $n$ there is $b$ with $d(b)\ge n$, since that means that for all $n$ there are numbers not reachable in $n$ steps, and it then follows by induction that for all $n$ there are numbers reachable in exactly $n$ steps, since at each stage of the induction there are adjacent numbers of which one is reachable in $n$ steps and the other isn't, and the latter can be reached in an $(n+1)$-th step of $1$.
Now represent the integers in "infinite two's complement", that is, a non-negative integer is represented by its binary representation and a negative integer $k$ is represented by inverting the binary representation of $-(k+1)$, considered as a leftward infinite string with leading zeros. This puts the integers into bijection with the set of all leftward infinite binary strings with finitely many transitions between $0$ and $1$.
In this representation, adding a positive integer to a number works as expected, with carrying carried out until the infinite stretch of $0$s or $1$s is reached, and the $1$s flipped to $0$s by a carry.
Now in each step, we can add a positive power of two to the number we've reached, and then we can optionally flip its sign. (This is equivalent to adding or subtracting powers of two at each step.) Since flipping the sign means inverting the string and then adding $1$, in each step we can invert the string and add a power of two up to twice.
Inverting the string doesn't change the number of transitions between $0$ and $1$. Adding a power of two increases the number of transitions between $0$ and $1$ by at most $2$. Thus in each step we can increase the number of transitions by at most $4$. Since there are integers whose representations have arbitrary numbers of transitions, for every $n$ there are integers we can't reach in $n$ steps.
