Bitwise Reversion

Bitwise AND is a lossy operation. It does not have some cute arithmetic inverse hiding in the bushes. The whole trick is to stop trying to reverse the full numbers and instead look at one bit at a time.

For every bit position, we need three bits $a_i,b_i,c_i$ such that:

$$a_i \& b_i = x_i$$ $$b_i \& c_i = y_i$$ $$a_i \& c_i = z_i$$

Since bitwise AND never mixes different bit positions, this local condition is enough. If every bit position is possible, the whole numbers are possible.

What does a target bit force?

If $x_i=1$, then $a_i\&b_i=1$, so both $a_i=1$ and $b_i=1$.

If $y_i=1$, then both $b_i=1$ and $c_i=1$.

If $z_i=1$, then both $a_i=1$ and $c_i=1$.

Now notice the annoying case: exactly two of $x_i,y_i,z_i$ are $1$.

Suppose $x_i=1$, $y_i=1$, and $z_i=0$.

From $x_i=1$, we need $a_i=1$ and $b_i=1$.

From $y_i=1$, we need $b_i=1$ and $c_i=1$.

So now $a_i=1$ and $c_i=1$, which forces:

$$a_i \& c_i = 1$$

That means $z_i$ must be $1$, contradiction. So $(1,1,0)$ is impossible.

By symmetry, $(1,0,1)$ and $(0,1,1)$ are also impossible.

The possible target patterns for one bit are:

• $(0,0,0)$: easy, set at most one of $a_i,b_i,c_i$ to $1$, or all zero.
• $(1,0,0)$: set $a_i=b_i=1$, $c_i=0$.
• $(0,1,0)$: set $b_i=c_i=1$, $a_i=0$.
• $(0,0,1)$: set $a_i=c_i=1$, $b_i=0$.
• $(1,1,1)$: set all three to $1$.

So the entire condition is:

No bit may be set in exactly two of $x,y,z$.

There are two nice ways to implement this.

Direct bad-bit check

A bit is bad if it appears in exactly two numbers:

$$(x \& y \& \sim z) \;|\; (x \& z \& \sim y) \;|\; (y \& z \& \sim x)$$

If that expression is nonzero, answer NO; otherwise answer YES.

Even cleaner construction check

Every bit that appears in $x$ must be in both $a$ and $b$.

Every bit that appears in $y$ must be in both $b$ and $c$.

Every bit that appears in $z$ must be in both $a$ and $c$.

So the forced minimal candidates are:

$$a = x \;|\; z$$ $$b = x \;|\; y$$ $$c = y \;|\; z$$

Then just check whether these actually work:

$$a \& b = x$$ $$b \& c = y$$ $$a \& c = z$$

If they work, answer YES. If not, some forbidden exactly-two-ones bit created an extra AND bit, so answer NO.

That is the whole problem. Tiny bitmask logic, zero drama.

Complexity: $O(1)$ per test case.