Sum of all powers of two
Consider the binary representation of $\,n+1 = 2^{k+1}+\sum_{j=0}^k b_j 2^j \;\mid\; b_j \in \{0,1\}\,$, then:
$$n = 2^{k+1}-1+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k 2^{j}+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k (b_j+1)2^j \quad \style{font-family:inherit}{\text{where}}\;\; b_j+1 \in \{1,2\}$$
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion: $$n = \delta_0 2^0 + \delta_1 2^1 + \ldots + \delta_k 2^k,$$ where $\delta_i \in \lbrace 0, 1\rbrace$. Take the least $m$ such that $\delta_i = 0$, and consider the least $l > m$ such that $\delta_l = 1$. Then, we can write: $$n = 2^0 + \ldots + 2^{m-1} + 2\cdot 2^m + 2^{m+1} + \ldots + 2^{l-1} + \delta_{l+1} 2^{l+1} + \ldots + \delta_k 2^k.$$ Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $\lfloor\log_2(n)\rfloor - m$, where $m$ is the start of the first gap.
Given any binary string $\overline{b_n\dots b_1b_0}(b_i\in \{0, 1\}, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10\mapsto 02$: If $\overline{b_{j +1}b_j} = 10$, let $\overline{b_{j +1}b_j} \gets02$.
- Delete the highest digit if it is 0.
- $20\mapsto 12$: If $\overline{b_{j +1}b_j} = 20$, let $\overline{b_{j +1}b_j} \gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = \max\{i\colon b_i = 0\}$ for string $\overline{b_n\dots b_1b_0}$, then $m \leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 \mapsto 102021 \mapsto 101221 \mapsto 021221 \mapsto 21221$.