SKETCH: It’s often useful to gather some numerical data:
$$\begin{array}{rcc}
n:&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18\\
k(n):&0&1&3&5&8&11&14&17&21&25&29&33&37&41&45&49&54&59\\
k(n)-k(n-1):&&1&2&2&3&3&3&3&4&4&4&4&4&4&4&4&5&5
\end{array}$$
Notice that the gaps in the bottom line are a single $1$, two $2$s, four $3$s, and eight $4$s. This suggests that if $2^{m-1}<n\le 2^m$, then $k(n)-k(n-1)=m$. Assuming this to be the case, we must have
$$k(2^m)=\sum_{\ell=1}^m\ell2^{\ell-1}=(m-1)2^m+1\;.$$
This can now be proved by induction on $m$, since $k(2n)=2n-1+2k(n)$. Now let $n=2^m+r$, where $0\le r<2^m$. Then the obvious conjecture is that
$$k(n)=k(2^m)+(m+1)r=(m-1)2^m+1+(m+1)r\;,$$
which again can be verified by induction, though the argument is a bit messier.
Note that $m=\lfloor\lg n\rfloor$, and $r=n-2^m$, so $m$ and $r$ are both readily obtained from $n$.