Sum of a decreasing geometric series of integers I'm trying to calculate the sum of integers that are being divided by two (applying the floor function if necessary): $n\mapsto \lfloor \frac{n}{2}\rfloor$.
Let $S(n)=n+\lfloor\frac{n}{2}\rfloor+\left\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\right\rfloor+\ldots$.
For example,
$$
\begin{align*}
S(100) &= 100 + 50 + 25 + 12 + 6 + 3 + 1 + 0 +\ldots\\
S(3) &= 3 + 1 + 0 + \ldots\\
S(1000) &= 1000 + 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 + 0 + \ldots\end{align*}
$$
I'm trying to find a closed form for $S(n)$, where $n\in \mathbb N$. Any ideas?
[Solution] A lot of great answers. Thanks!
Here's my java implementation.
int computeHalvesSum(int n) {
  return 2 * n - Integer.bitCount(n)
}

 A: See OEIS sequence A005187  and references there.
Depending on what language you're using, the simplest way to compute it may be
as $2n - (\text{sum of binary digits of }n)$.
A: I don't know if it meets your criteria for an analytic solution, but 
$$
S(n)\sum_{k=0}^{\lfloor \log_2 n\rfloor} \left\lfloor\frac{n}{2^k}\right\rfloor
$$
The calculation of $\log_2$ probably means this is not worth implementing (you added that comment while I was writing my answer).
A: Let $n$ be the number in question, and $m$ be the number of $1$'s in the binary expansion of $n$.  For example, if $n=100_{10}=1100100_2$, so $m=3$.
Then the sum you seek is $$S(n)=2n-m$$
This is not constant time in $n$, but it is $O(\log n)$, which is pretty good.  I doubt you'll be able to do any better than that, since just writing down the answer takes $O(\log n)$ time.
A: Let $f(n)$ be the number of $1$s in the binary representation of $n$.  Then $S(n)=2n-f(n)$.
To see this: If there is a $1$ in the $2^k$ place in the binary expansion of $n$, then that $1$ contributes $2^k+2^{k-1}+\cdots+2^1+2^0=2^{k+1}-1$ to $S(n)$.  
Each contribution is one less than twice the place value of its $1$.  So the total contribution is $2n$ minus the number of $1$s in the binary representation of $n$.
