We prove by induction that even numbers at most $2^{2k}$ can be represented with at most $3k-1$ digits $2$ and even numbers at most $2^{2k-1}$ can be represented with at most $3k-2$ digits $2$. This is obviously true for $k=1$ with $2=2$ and $4=2\times2$. Now assume that it is already true for all exponents of $2$ smaller than a fixed $r$. We take a number $n$ in the appropriate range. If the number is divisible by 4, we apply the induction hypothesis to $n/2$ and multiply the expression by 2. If not, one of $n\pm 2$ is a multiple of 8. We apply the induction hypothesis to $(n\pm 2)/2/2$ and need 3 digits 2 to go to $n$ which is exactly the needed induction step. In particular, even numbers at most $2^{11}=2048$ can be represented with 16 digits 2, and odd numbers at most $2^{11}$ are $\pm 2/2 + 2\times(2m)$ where $2m$ is an even number smaller than $2^{10}$ which can be represented by $14$ digits. So 17 digits 2 always suffice. Note that going downwards adding and subtracting ones or twos always corresponds to rounding to some multiple of 4 or 8, so we can never jump a power of 2 by these operations and the bounds needed in the induction are not exceeded.

This is very tricky to write it up. Not sure if the following is understandable. The main lemma is the following. Lemma: Every positive integer $n$ can be expressed in form $2^{a_1}\pm 2^{a_2} \pm 2^{a_3} \pm \hdots \pm 2^{a_k}$ where signs are arbitrarily chosen so that $a_2-a_1, a_3-a_2,\hdots,a_k-a_{k-1} > 1$. Proof: Begin by expressing $n$ in base two. Then working from right to left, if there are same or consecutive power of two, we transform using the following operation. \begin{align*} 2^{m+1} + 2^m &\to 2^{m+2} - 2^m \\ 2^{m+1} - 2^m &\to 2^m \\ 2^m + 2^m &\to 2^{m+1} \\ 2^m - 2^m &\to \text{none} \end{align*}The process must eventually terminates as we cannot goes through any term higher than $2^{\log_2 n + 1}$. The construction is proceeded through Horner's method of evaluating polynomial. First, by the lemma, we can express $n$ as the sum or difference of at most six power of twos. We split $2^0$ out first (if exists) and replace it with $2\div 2$. Then we construct the rest of the representation by the following method, which clearly generalizes. \begin{align*} 1580 &= 2^{11} - 2^9 + 2^6 - 2^4 - 2^2\\ &= 2\times (-2 + (2\times 2 \times (-2 + (2\times 2\times (2 + (2\times 2 \times 2 \times (-2 + (2\times 2\times 2)))))))) \end{align*}It's clear that we used at most $11+5 = 16$ (if there is no $2^0$) or $11+4+2 = 17$ (if there is $2^0$).

It looks like you will end up at the same expression as me

MarkBcc168 wrote: This is very tricky to write it up. Not sure if the following is understandable. The main lemma is the following. Lemma: Every positive integer $n$ can be expressed in form $2^{a_1}\pm 2^{a_2} \pm 2^{a_3} \pm \hdots \pm 2^{a_k}$ where signs are arbitrarily chosen so that $a_2-a_1, a_3-a_2,\hdots,a_k-a_{k-1} > 1$. Proof: Begin by expressing $n$ in base two. Then working from right to left, if there are same or consecutive power of two, we transform using the following operation. \begin{align*} 2^{m+1} + 2^m &\to 2^{m+2} - 2^m \\ 2^{m+1} - 2^m &\to 2^m \\ 2^m + 2^m &\to 2^{m+1} \\ 2^m - 2^m &\to \text{none} \end{align*}The process must eventually terminates as we cannot goes through any term higher than $2^{\log_2 n + 1}$. The construction is proceeded through Horner's method of evaluating polynomial. First, by the lemma, we can express $n$ as the sum or difference of at most six power of twos. We split $2^0$ out first (if exists) and replace it with $2\div 2$. Then we construct the rest of the representation by the following method, which clearly generalizes. \begin{align*} 1580 &= 2^{11} - 2^9 + 2^6 - 2^4 - 2^2\\ &= 2\times (-2 + (2\times 2 \times (-2 + (2\times 2\times (2 + (2\times 2 \times 2 \times (-2 + (2\times 2\times 2)))))))) \end{align*}It's clear that we used at most $11+5 = 16$ (if there is no $2^0$) or $11+4+2 = 17$ (if there is $2^0$). Unary minus is not allowed, you should (and you can) change your expressions a bit.