We can add do the following operations
a) add 1 to number
b) multiply number by 2
By using only a) and b) operations we can get any number from 0.
How much operations we need to do at least to get N?
We can add do the following operations
a) add 1 to number
b) multiply number by 2
By using only a) and b) operations we can get any number from 0.
How much operations we need to do at least to get N?
Write $N\ge0$ in binary. Let $d_0(N)$ be the number of zeroes and $d_1(N)$ be the number of ones.
Claim: The minimal number of steps is $s(N):=d_0(N)+2d_1(N)-1$.
Proof: This is true for $N=0$, where $d_1(N)=0$, $d_0(N)=1$ and we need $0$ steps.
If $N=2k+1$ is odd, the last step must be addition of one. Hence to produce $N$ we must first produce $2k$, then add one. Note that $d_0(N)=d_0(2k)-1$, $d_1(N)=d_1(2k)+1$ and hence $s(N)=s(2k)+1$. Since $s(2k)$ is the minmal number of steps to produce $2k$, we conclude that $s(N)$ is the number of steps needed for $N$.
If $N\ge 2$ is even, we have two options: Produce $N-1$ and add one. Or produce $\frac N2$ and double. For the second method, we observe that $d_1(N)=d_1(\frac N2)$ and $d_0(N)=d_0(\frac N2)+1$ (this requires $N\ge2$), hence $s(N)=s(\frac N2)+1$. Thus we need to show that the path via $N-1$ cannot be better. If $N=2^r$ is a power of $2$ with $r\ge1$, note that $d_0(N)=r$, $d_1(N)=1$, $d_0(N-1)=0$, $d_1(N-1)=r$, hence $s(N)=r+1$, $s(N-1)=2r-1$. Thus $s(N)=s(N-1)+1$ if $r=1$ (i.e. we have a free choice to double or add in order to obtain $2$ from $1$), whereas $s(N) for $r>1$ (i.e. the straightforward method via $\frac N2$ is strictly faster than the method via $N-1$). If $N=2^ru$ with $r\ge 1$ and $u>1$ odd, we have $d_0(N)=d_0(N-1)+r-1$, $d_1(N)=d_1(N-1)-r+1$, hence $s(N)=s(N-1)-r+1\le s(N-1)$. Therefore $s(N-1)+1>s(N)$, i.e. the method via $N-1$ is strictly slower than the method via $\frac N2$. $_\square$
Think binary. If you write $N$ in binary notation, then multiplying by 2 simply shifts digits one space to the left and appends zero on the right. Thus, in at most two operations per binary digit of $N$, and working from the leftmost digits to the right, we could get from $0$ to $N$. That's at most $2 \lfloor \log_2 N \rfloor$ operations.
Here's an illustration with $N = 29$. In binary, $N = 11101$.
$\begin{array}{ll} \textrm{start} & 0 \\ (+1) & 1 \\ (\times 2) & 10 \\ (+1) & 11 \\ (\times 2) & 110 \\ (+1) & 111 \\ (\times 2) & 1110 \\ (\times 2) & 11100 \\ (+1) & 11101 \\ \end{array}$