https://spherical-harmonics.hatenablog.com/entry/2019/01/09/171824

${}_nC_{r}$ の偶奇について考えたのは、2013年頃の話で、当時の結論は、

${}_\mod (nC_{r},2)$ の値はビット演算子を用いて

n == ( r | (n - r) )

となる。

というものだ。例えば、 ${}_5C_{2}=10$ は偶数だが、

( 10 | 11 ) = 11

は101ではないので、命題は偽となり、値は0となる。また ${}_6C_{2}=15$ は奇数だが、

( 10 | 100 ) ) = 110

により命題は真となり、値は1となる。という具合である。
この方法なら、大きな数に対する二項係数の偶奇もあっという間に計算できる。

何故、これで良いのかについて書こう。

(1) $n!$ が持つ素因数2の個数 $f(n)$ は $\displaystyle\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2^2} \rfloor + \lfloor \frac{n}{2^3} \rfloor +\cdots$ である。

ちなみに、これは $n$ を2進数表示したときの $2^k$ の位の数を $g_n(k)\in \{0,1\}$ とし、 $n$ が $l$ 桁の2進数するとき、 $\displaystyle f(n)=\sum_{k=0}^{l-1} (2^{k}-1)g_n(k)$ と表現できる。

(2) $f(a+b)\geq f(a)+f(b)$ である。これは一般に $\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloor$ または
$\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloor+1$ となることからわかる。

(3) $f(a+b)\geq f(a)+f(b)$ の等号成立は $\displaystyle\lfloor \frac{a+b}{2^k} \rfloor =\lfloor \frac{a}{2^k} \rfloor+\lfloor \frac{b}{2^k} \rfloor$ が任意の $k$ について成立することだから、 $k$ が大きい順に考えていくと、任意の $l$ について $g_l(a+b)=g_l(a)+g_l(b)$ が成立することである。つまり、2進数における $a+b$ の筆算において繰り上がりが生じないことが必要十分条件となる。

(4)繰り上がりが生じない2進数の筆算においては、 $0+0=0,0+1=1,1+0=1$ の3つしか登場せず、 $1+1=10$ は登場しない。よって、足し算とビット毎の or 演算が等価となる。つまりビット演算子「OR」を用いて $a+b= (a$ OR $b)$ と表現することができる。XOR でも構わない。

(5) ${}_nC_{r}$ が奇数である必要十分条件は $f(n)=f(r)+f(n-r)$ であるから $n+(n-r)= (n$ OR $(n-r))$ となる。

(2019.1.12追記)
spherical-harmonics.hatenablog.com
により、

(6) この条件は $n$ XOR $r$ XOR $(n-r)$ =0 となる。