Number of non-XOR gates needed to implement an n-bit boolean function
By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C_{n,k}$.

We upper bound $C_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align}
2^{2^n}
&amp;\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}
\\
&amp;= 2^{n+k+1} \prod_{i=1}^k 4^{n+i}
\\
&amp;= 2^{n+k+1} 4^{\sum_{i=1}^k n+i}
\\
&amp;= 2^{n+k+1} 4^{kn + k(k+1)/2}
\\
&amp;= 2^{2kn + k^2 + 2k + n + 1}
\end{align}$$

Now we start manipulating both sides:

$$\begin{align}
2^{2^n} &amp;\leq 2^{2kn + k^2 + 2k + n + 1}
\\
2^n &amp;\leq 2kn + k^2 + 2k + n + 1
\\
0 &amp;\leq k^2 + k(2n + 2) + (n + 1 - 2^n)
\end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align}
k &amp;= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2}
\\
  &amp;= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1}
\\
  &amp;= -n - 1 \pm \sqrt{n^2 + n + 2^n}
\\
  &amp;\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right)
\\
  &amp;= \Omega \left(\sqrt{2^n} \right)
\\
\end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.