Solving linear recurrences with repertoire method $$\begin{align*}
A_1 &= 0\\
A_{2n} &= 3A_n + n\\
A_{2n+1} &= 3A_n + n
\end{align*}$$
I am trying to solve a recurrence of this form, after writing out small number I can see no pattern except it should be related to $3^{\lfloor\log n\rfloor}$. And if I try to apply the repertoire method, I find myself stuck because no matter which function i try to plug in, the coefficient $3$ just get in the way because the cases are divided into even and odd
Can someone give me a hint or some help?

Write $n$ in binary, so $n=\sum_{k=0}^ma_k2^k$, with each $a_k$ either $0$ or $1$, and $a_m=1$.
Firstly, if $n=2^m$, there is a simple formula for $A_n$ in terms of powers of $2$ and $3$.
Secondly, if $n=2^m+2^p$, with $p<m$, see how the final value is adjusted by the $2^p$
In general, find a formula for $A_n$ in terms of the $a_k$.  
