Number of times statement is executed in complex nested loop
We can determine the exact value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:


  $s \leftarrow s+n-k$


At the end of the program we'll have:

$$
s= \sum_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor
$$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$
n = \sum_{u \in S} 2^u
$$

for some $S \subseteq \mathbb{N}_{\le \lambda}$.

Therefore we have:

$$
\sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum_{h=0}^{\lambda} \sum_{u \in S} \left \lfloor 2^{u-h} \right \rfloor =  \sum_{u \in S} \sum_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor =
\sum_{u \in S} 2^{u+1} -1
$$

But then:

$$
\sum_{u \in S} 2^{u+1} -1 = 2n - |S|
$$

Piercing it all together, at the end of the program we will have:

$$
s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n)
$$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.