Is it possible to calculate $card \{ (x, y) | xy = (x \& y) (x | y) \}$, where $x, y$ are integers>=0 in $[a, b]$ and $\&, |$ are bitwise AND and OR?

Question

I saw a programming task of calculating $card \{ (x, y) | x * y= (x \& y) * (x | y) \}$ where $x, y \in [ 0, 31 ]$, then I came up with a thought: is this workable by Maths?

Answer 1

With $c=x\mathop\&y$, we have $x=a+c$, $y=b+c$, $x\mathop| y=a+b+c$, where $a,b,c$ are "bit-disjoint". The condition then reads $$(a+c)(b+c)=c(a+b+c)$$ and simplifies to $$ab=0. $$ Thus at least one of $a,b$ must be $=0$, in other words, one of $x,y$ must be a "bit-subset" of the other. If the range in question is $[0,2^n-1]$, we find pairs with "$x\subseteq y$" by having three choices for each of the $n$ bits: is not in $y$, is in $y$ but not $x$, is in $x$ (and $y$). This gives us $3^n$ pairs. Likewise, we have $3^n$ pairs with "$y\subseteq x$". But we counted the $2^n$ cases with $x=y$ twice, hence the final answer is $$ 2\cdot 3^n-2^n.$$