Lemma - Dyadic (XOR) Convolution Theorem

Note1: This lemma is used to prove the Dyadic Convolution Theorem.

Note2: To understand this proof, you should have a good understanding of Bit-wise operators. The first answer of this question has a nice explanation in case you need it.

Lemma Let $n(k)$ count the number of $1$s in the binary expansion of the non-negative integer $k$. We then claim that $n(i)+n(j)$ and $n(i \oplus j)$ have the same parity. Here again $\oplus$ denote the BitXOR operator.

(In the following proof, we use $'\&'$ to denote BitAND and $'|'$ to denote BitOR)

Proof It suffices to prove that $n(i)+n(j)-n(i\oplus j)$ is even. To do this, we find $n(i|j)$ in two ways. First, $i|j$ has a 0 if both bits of $i$ and $j$ in a position are 0, while otherwise it has a 1. Therefore,

$n(i|j)=n(i \oplus j)+n(i\&j)$

Here, $n(i \oplus j)$ counts the number of 1's in positions that has a 1 in exactly one of two numbers $i$ and $j$, while $n(i\&j)$ counts the number of 1's in positions that has a 1 in both the numbers.

On the other hand, we can simply use the inclusion-exclusion principle to compute $n(i|j)$. Here we have,

$n(i|j)=n(i)+n(j)-n(i\&j)$

Equating the two we get, $n(i)+n(j)-n(i\oplus j)=2\text{ }n(i\&j)$. $\blacksquare$