Smallest number of steps to reach from X to Y You are provided a number X and another number Y.
You can apply only the following operations : -
a) If the number is even, either double the number or increase it by 1.
b) If the number is odd, either double the number or decrease it by 1.  
What should be the minimum number of steps to convert X to Y?    
For example - If $X = 4$, and $Y = 11$ , the answer is $3$.
$4\to 5\to 10\to 11$.  
There can be cases where answer is not reachable at all like $X=4, Y=6$.
 A: In binary, you can either toggle the least significant bit or append a 0 bit.
Consequently, there is (up to loops) only one way to get from an $n$-bit number $X$ to an $m$-bit number $Y$: 


*

*If $n>m$ or the first $n-1$ bits of $X$ differ from the first $n-1$ bits of $Y$, no solution is possible. Terminate

*ensure that the first $n$ bits of $X$ are the same as the first $n$ bits of $Y$ by toggling if necessary.

*If you have reached $Y$, terminate

*Double $X$ and go back to step 2.


The number of operations performed is apparently: $m-n$ to account for all doublings, plus the number of $1$'s in the lower $m-n$ bits of $Y$, plus possibly $1$ is the least significant of $X$ starts out wrong.
A: Note that we can "toggle" between the values $ 2n \leftrightarrow 2n+1 $ and otherwise the only operation is to double a value.
Let $X$ have the binary representation $a_0 a_1 \cdots  a_{n-1} a_n$ and $Y$ have a binary representation $b_0 b_1 \cdots b_{n-1} b_n \cdots b_m $. $Y$ can only be reached from $X$ if $ a_i =b_i$ for $i=0, \cdots n-1$ and this can be achieved in $ n_0 + 2n_1 + \alpha $ steps. Where $n_0$ is the number of zeros in $b_{n+1} \cdots b_m $ , $n_1$ is the number of ones in $b_{n+1} \cdots b_m $ and $ \alpha $ is zero or one according to weather $a_n$ and $b_n$ are equal or unequal respectively.  
