Answer: $\frac{3^{n}+1}{2}$
Solution 1: Note that $a_{2^{n}-1}=1$ for all $n$ by repeatedly applying $a_{2 i+1}=a_{i}$. Now let $b_{n}=$ $a_{0}+a_{1}+a_{2}+\cdots+a_{2^{n}-1}$. Applying the given recursion to every term of $b_{n}$ except $a_{0}$ gives
$$\begin{aligned} b_{n}= & a_{0}+a_{1}+a_{2}+a_{3}+\cdots+a_{2^{n}-1} \\ = & a_{0}+a_{2}+a_{4}+\cdots+a_{2^{n}-2}+a_{1}+a_{3}+\cdots+a_{2^{n}-1} \\ = & a_{0}+\left(a_{0}+a_{1}\right)+\left(a_{1}+a_{2}\right)+\left(a_{2}+a_{3}\right)+\cdots+\left(a_{2^{n-1}-2}+a_{2^{n-1}-1}\right) \\ & +a_{0}+a_{1}+a_{2}+\cdots+a_{2^{n-1}-1} \\ = & 3 a_{0}+3 a_{1}+3 a_{2}+\cdots+3 a_{2^{n-1}-2}+3 a_{2^{n-1}-1}-a_{2^{n-1}-1} \\ = & 3 b_{n-1}-1 . \end{aligned}$$

Now we easily obtain $b_{n}=\frac{3^{n}+1}{2}$ by induction.
Solution 2: Define a binary string to be good if it is the null string or of the form $101010 \ldots 10$. Let $c_{n}$ be the number of good subsequences of $n$ when written in binary form. We see $c_{0}=1$ and $c_{2 n+1}=c_{n}$ because the trailing 1 in $2 n+1$ cannot be part of a good subsequence. Furthermore, $c_{2 n+2}-c_{n+1}$ equals the number of good subsequences of $2 n+2$ that use the trailing 0 in $2 n+2$. We will show that this number is exactly $c_{n}$.
Let $s$ be a good subsequence of $2 n+2$ that contains the trailing 0 . If $s$ uses the last 1 , remove both the last 1 and the trailing 0 from $s$; the result $s^{\prime}$ will be a good subsequence of $n$. If $s$ does not use the last 1 , consider the sequence $s^{\prime}$ where the trailing 0 in $2 n+2$ is replaced by the last 0 in $n$ (which is at the same position as the last 1 in $2 n+2$.) The map $s \mapsto s^{\prime}$ can be seen to be a bijection, and thus $c_{2 n+2}=c_{n}+c_{n+1}$.
Now it is clear that $a_{n}=c_{n}$ for all $n$. Consider choosing each binary string between 0 and $2^{n}-1$ with equal probability. The probability that a given subsequence of length $2 k$ is good is $\frac{1}{2^{2 k}}$. There are $\binom{n}{2 k}$ subsequences of length $2 k$, so by linearity of expectation, the total expected number of good subsequences is
$$\sum_{k=0}^{\lfloor n / 2\rfloor} \frac{\binom{n}{2 k}}{2^{2 k}}=\frac{(1+1 / 2)^{n}+(1-1 / 2)^{n}}{2}=\frac{3^{n}+1}{2^{n+1}} .$$

This is equal to the average of $a_{0}, \ldots, a_{2^{n}-1}$, therefore the sum $a_{0}+\cdots+a_{2^{n}-1}$ is $\frac{3^{n}+1}{2}$.