Parity of binomial coefficients

Consider the binomial coefficient C(n,m) = n*(n-1)*...*(n-m+1)/(m*(m-1)*...*2*1).  When is this number odd and when is it even?  In this post, we use Lucas' theorem to provides a simple characterization of this.  Lucas' theorem states that for integers $m$, $n$ and prime $p$, the following relationship holds:
\[ C(n,m) \equiv \prod_{i=0}^{k} C(n_i, m_i) \mod  p \]
where $n_i$ and $m_i$ are the digits of $n$ and $m$ in base $p$ respectively, with $n_0$ and $m_0$ being the least significant digits.

When $p=2$, $n_i$ and $m_i$ are the bits in the binary expansion of $n$ and $m$ and $C(n_i, m_i)$ is $0$ if and only if $n_i < m_i$. This implies that $C(n,m) \equiv 0 \mod 2$ if and only if  $n_i < m_i$ for some $i$.

The truth table for  $n_i < m_i$ is:

\[\begin{array}{ c | c || c }
  n_i & m_i & n_i < m_i \\ \hline
  0 & 0 & 0 \\
  0 & 1 & 1 \\
  1 & 0 & 0 \\
  1 & 1 & 0 \\
\end{array}\]

i.e., it is logically equivalent to $m_i AND ( NOT n_i)$.  If we think of $AND$ and $NOT$ as bitwise operations on the binary representation of numbers, then we have shown that:

$C(n,m) \equiv 0 \mod 2$ if and only if $m AND ( NOT n)$ is not zero.

A simple Python function that implements this statement is

def bincoefmod2(n,m): 
# computes binomial(n,m) mod 2
    return 0 if ~n & m else 1

or equivalently:

def bincoefmod2(n,m): 
# computes binomial(n,m) mod 2
    return int(not ~n & m)


Incidentally, for bits $n_i$ and $m_i$, $n_i < m_i$ is logically equivalent to $NOT (m_i\Rightarrow n_i)$.

Next we consider C(n,m)C(a,b) mod 2.  Clearly this is equivalent (mod 2)  to (C(n,m) mod 2)*(C(a,b) mod 2).  Thus $C(n,m)C(a,b) \equiv 0 mod 2$ if and only if $m AND ( NOT n)$ is not zero or $b AND ( NOT a)$  is not zero.  This in turns implies the following:

\[\begin{array}{l}
C(n,m)C(a,b) \equiv 0 mod 2 \Leftrightarrow \\
(m AND ( NOT n)) OR (b AND ( NOT a)) \ne 0
\end{array}\]

where OR is a bitwise operation. The corresponding Python function is:


def bincoefprodmod2(n,m,a,b): 
# computes binomial(n,m)*binomial(a,b) mod 2
    return 0 if (~n & m)|(~a & b) else 1

or equivalently:
def bincoefprodmod2(n,m,a,b): 
# computes binomial(n,m)*binomial(a,b) mod 2
    return int(not (~n & m)|(~a & b))