CMIMC 2019 Team Problem 14

Consider the following function:

1: \ \textbf{procedure } M(x)
2: \ \quad \textbf{if } 0 \leq x \leq 1 \textbf{ then}
3: \ \quad \quad \textbf{return } x
4: \ \quad \textbf{return } M(x^{2} \bmod 2^{32})

Let f: \mathbb{N} \rightarrow \mathbb{N} be defined such that f(x)=0 if \mathrm{M}(x) does not terminate, and otherwise f(x) equals the number of calls made to M during the running of \mathrm{M}(x), not including the initial call. For example, f(1)=0 and f\left(2^{31}\right)=1. Compute the number of ones in the binary expansion of

f(0)+f(1)+f(2)+\cdots+f\left(2^{32}-1\right)