I know that $\frac{1}{2}(-1+2^{-n}(n+1)$$n \choose k$), where k = $\frac{n+1}{2}$, is the formula for calculating this, and I know that $n \choose k$ means $\frac{n!}{k!(n-k)!}$, but calculating $\frac{n!}{k!(n-k)!}$ for very large values of $n$ is time consuming, particularly when the results are too big for the computer's floating point processor to handle, in which case you have to use a special floating point library to deal with it.
I have written a program to solve this, and I made the code that solves $\frac{n!}{k!(n-k)!}$ to do a minimum number of multiplications. It takes about 15 seconds to give the solution for $n = 1000001$ as $398.4425796$, and because I wrote the 'very big number' handing routines myself, I'm not 100% sure my answer is correct to the number of decimal places I have given. Is there an elegant way to do this calculation a lot faster and preferably one that doesn't produce intermediate calculations that the computer's fp processor can't handle?
You can use Stirling’s series to approximate the factorials. For the precision you’re after, you should include the $\frac1n$ term to be on the safe side:
$$\log n!=n(\log n-1)+\frac12\log(2\pi n)+\frac1{12n}+O\left(\frac1{n^3}\right)\;.$$
This yields
\begin{eqnarray} \log\binom n{\frac{n+1}2}&\approx&n(\log n-1)+\frac12\log(2\pi n)+\frac1{12n}\\&&-\left(\left(\frac{n+1}2\right)\left(\log\left(\frac{n+1}2\right)-1\right)+\frac12\log\left(2\pi\frac{n+1}2\right)+\frac1{12\left(\frac{n+1}2\right)}\right) \\&&-\left(\left(\frac{n-1}2\right)\left(\log\left(\frac{n-1}2\right)-1\right)+\frac12\log\left(2\pi\frac{n-1}2\right)+\frac1{12\left(\frac{n-1}2\right)}\right) \\ &=& n\log2-\left(\frac{n+1}2\right)\log\left(1+\frac1n\right) -\left(\frac{n-1}2\right)\log\left(1-\frac1n\right) -\frac12\log(2\pi n)\\ &&+\log2-\frac12\log\left(1+\frac1n\right)-\frac12\log\left(1-\frac1n\right)+\frac1{12}\left(\frac1n-\frac2{n+1}-\frac2{n-1}\right) \\ &\approx& (n+1)\log2-\frac{n+1}2\left(\frac1n-\frac1{2n^2}\right)+\frac{n-1}2\left(\frac1n+\frac1{2n^2}\right)-\frac12\log(2\pi n)-\frac1{4n} \\ &\approx& (n+1)\log2-\frac12\log(2\pi n)-\frac3{4n}\;. \end{eqnarray}
Together with the rest of your formula (except for the $-\frac12$), this yields the approximation
$$-(n+1)\log2+\log(n+1)+(n+1)\log2-\frac12\log(2\pi n)-\frac3{4n}\approx\bbox[5px, border: 1px solid green]{\frac12\log\frac n{2\pi}+\frac1{4n}}$$
for the logarithm of the expected number of zero crossings. For $n=1000001$, this is
$$ \frac12\log\frac{1000001}{2\pi}+\frac1{4\cdot1000001}\approx5.988817495776964\;, $$
corresponding to an expected number of approximately
$$ 398.44257960805571 $$
zero crossings (now with $-\frac12$ included), in agreement with your result. This agrees in all digits with the value produced by Wolfram|Alpha. I thought I discarded terms of order $\frac1{n^2}$, but this seems to be accurate up to that order, so either Wolfram|Alpha also only uses an expansion up to order $\frac1n$ for that calculation, or the discarded terms of order $\frac1{n^2}$ cancel out. Wolfram|Alpha also returns the above approximation up to order $\frac1n$; unfortunately, clicking on “More terms” doesn’t actually produce more terms.