Double-nested loop with bitwise operation
The number of foo() calls is the number of 1 bits in all numbers from 0 to $n$ (or all even numbers between $0$ and $2n$ - same thing). Asymptotically, it's $O(n \log n)$, because the number of 1 bits is around $\log_2(n)/2$.

I don't have an exact function. It won't be a smooth function - for example, $f(1023)-f(1022)=10$, but $f(1024)-f(1023)=1.$