组合数可以表示为

\[C^m_n = \frac{n!}{m!(n-m)!} \]

假设\(n!,m!,(n-m)!\)含因子\(2\)的个数分别为\(A,B,C\)
则当\(A=B+C\)时，\(C^m_n\)为奇数

那么如何求出\(n!\)的因子个数呢？
对于一个质数\(p\)，
它的倍数\(k*p^i\)含因子\(p\)的个数为即为\(i(k=1,2,3...)\)
于是只要求出\(n!\)中所有的\(k*p^i\)即可，
则\(n!\)含因子\(p\)的个数为

\[\lfloor \frac{n}{p} + \frac{n}{p^2} + \frac{n}{p^3} + \frac{n}{p^4} + ... \rfloor \]

所以\(n!\)含因子\(2\)的个数为

\[f(n) = \lfloor \frac{n}{2} + \frac{n}{2^2} + \frac{n}{2^3} + \frac{n}{2^4} + ... \rfloor \]

其中，可以将\(n\)表示为二进制拆分的形式：

\[n = (a_1*2^0)+ (a_2*2^1)+ (a_3*2^2)+ (a_4*2^3)+... \]

则\(f(n)\)就可以表示成

\[f(n) = \sum \limits_{j=1}^{k} \frac{(a_1*2^0)+(a_2*2^1)+...+ (a_k*2^{k-1})}{2^j} \]

将式子简化

\[= \sum \limits_{j=1}^{k} \frac{(a_{j-1}*2^j)+...+ (a_k*2^{k-1})}{2^j} \]

\[= \sum \limits_{j=1}^{k} \sum \limits_{i=j+1}^{k} \frac{a_{i}*2^{i-1}}{2^j} \]

\[= \sum\limits_{i=1}^{k} a_i \sum\limits_{j=1}^{i-1} \frac{2^{i-1}}{2^j} \]

\[= \sum\limits_{i=1}^{k} a_i \sum\limits_{j=0}^{i-2} 2^j \]

\[= \sum\limits_{i=1}^{k} a_i * (2^{i-1} - 1) \]

\[= \sum\limits_{i=1}^{k} a_i * 2^{i-1} - \sum\limits_{i=1}^{k} a_i \]

\[= n - \sum\limits_{i=1}^{k} a_i \]

观察这个式子，可以发现

\[\sum\limits_{i=1}^{k} a_i = n在二进制下1的个数 \]

设\(n,m,(n-m)\)在二进制下\(1\)的数目分别为\(a,b,c\)
要满足\(A=B+C\)，则：

\[n−a=m−b+(n−m)−c \]

\[a=b+c \]

要满足这个条件则有

\[(n\&m) == m \]