Add = XOR

以下では $N$ を二進数として扱うこととします。

$N = 1010$ の時について考えます。

XOR の演算では各桁を独立に考えますが、足し算の場合は繰り上がりがあります。 $X + Y$ で繰り上がりのある桁がある場合、$X + Y = X \oplus Y$ を満たすことはできません。 そのため、$X, Y$ 両方において $1$ である桁は存在しません。 よって、$N$ において $0$ である桁は $X, Y$ どちらも $0$ である必要があります。 対して、$N$ において $1$ である桁は、$X, Y$ どちらかが $1,$ 一方が $0$ である必要があります。 これが $2$ 通りで、各桁を独立に考えることができるため、$N$ において $1$ である桁の数が $p$ 個存在する場合、 $X + Y = X \oplus Y$ を満たす非負整数 $(X, Y)$ の組は $2 ^ p$ 組存在します。 ただし、この中には $(N, 0), (0, N)$ もしくは $(0, 0)$ が含まれ、条件を満たさないこれらを除く必要があります。