What is the minimum number of moves to change $a$ into $b$ by doubling and halving? We are given integers $a$ and $b$, and wish to change $a$ to $b$ using these operations:
(1) Map $a \mapsto \lfloor \frac{a}{2} \rfloor$. (If $a$ is even, replace it with $\frac{a}{2}$. If $a$ is odd, replace it with $\frac{a − 1}{2}$.)
(2) Map $a \mapsto 2a$ (multiply $a$ by $2$).
What is the fewest number of operations required to get $a$ equal to $b$?
Also, $\boldsymbol{b}$ is always a power of 2.

Examples:


*

*$a = 3$, $b = 8$: answer is $4$.

*$a=4$, $b=1$: answer is $2$.
 A: Write $a$ and $b$ into binary system.
Note that the operation (1) is to remove the last binary digit, and the operation (2) is to append a zero to the end.
So, arriving to $b$ is possible if and only if $b$ and $a$ begin with the same chain of $1$'s and $0$'s, and after this common part, $b$ has no ones. Note that no operation allows us to add ones.
The number of steps, when possible, is the number of digits that we need to remove from $a$ plus the number of zeros that has $b$ after the common part.
Example: $a=55$, $b=104$.
In binary: $a=110101$, $b=1101000$. We see that the longest possible common starting chain is $11010$, so we remove the last digit from $a$, that is, we make the operation (1) once. After that we add two zeros, that is, we make the operation (2) twice. This makes three steps.
Example: $a=24$, $b=26$.
In binary: $a=11000$, $b=11010$. This case is impossible because after the common starting chain ($110$) the number $b$ has an one.
EDIT: This method can be easily applied in the particular case that $b$ is a power of two. Under this assumption, the algorithm always works, because any pair of positive integer numbers has a common starting chain when written into binary (namely $1$) and $b$ has only zeros after this starting one.
A: There are some cases where you cannot change $a$ into $b$ at all; for example $a = 3$ cannot be changed into $b = 5$.
In general, write $a$ in binary: $a = a_0 a_1 a_2 \ldots a_k $, where $a_i \in \{0,1\}$.
Also write $b$ in binary: $b = b_0 b_1 b_2 \ldots b_l$, $b_i \in \{0,1\}$. Then:


*

*The map $a \mapsto \lfloor \frac{a}{2} \rfloor$ deletes the last digit of $a$.

*The map $a \mapsto 2a$ adds a zero at the end of $a$.
Now, let $\boldsymbol{i}$ be the largest index such that $\boldsymbol{b_0 b_1 b_2 \ldots b_i}$ is an initial segment of $\boldsymbol{a}$.
In particular, $0 \le i \le \min(k,l)$.
We have the following cases:


*

*Suppose that $b_{i+1}, b_{i+2}, \ldots, b_l$ are not all zero.
Then it is impossible to change $a$ into $b$ by any sequence of moves.

*Suppose on the other hand that $b_{i+1}, b_{i+2}, \ldots, b_l$ are all zeroes.
Then it is possible, and the best we can do to transform $a$ into $b$ is to remove things from the end of $a$ (do the move $a \mapsto \lfloor \frac{a}{2} \rfloor$) until we get $b_0 b_1 b_2 \ldots b_i$, and then add zeros at the end (do the move $a \mapsto 2a$) until we get $b$.
So the fewest number of moves is given by
$$
\underbrace{(k - i)}_{\text{digits removed from end of $a$}}
+ \underbrace{(l - i)}_{\text{zeros appended to the result to arrive at $b$}}
= k + l - 2i.
$$
A: It makes no sense to perform a double followed by a halve, because this leaves you where you started from. So you halve $a$ until it is a power of two; then you double or halve the result until it is equal to $b$.
