Reverse XOR

Let $x$ have binary length $L$. Write its bits from least significant to most significant as

$a_0,a_1,\dots,a_{L-1}$

with $a_{L-1}=1$.

Reversing the binary representation means that, if we still view $f(x)$ using exactly $L$ padded bits, its bit at position $i$ is $a_{L-1-i}$.

So if

$n=x\oplus f(x),$

then the $i$-th bit of $n$, padded to length $L$, is

$b_i=a_i\oplus a_{L-1-i}.$

Now the whole problem basically folds in half.

The symmetry

Because XOR is symmetric,

$b_i=a_i\oplus a_{L-1-i}=a_{L-1-i}\oplus a_i=b_{L-1-i}.$

So the padded binary representation of $n$ must be a palindrome.

Example: $6=110_2$. Add one leading zero and get $0110$, which is a palindrome, so $6$ is possible.

Example: $8=1000_2$. The tempting padded palindrome is $0001000$, but that has a problem we still need to catch.

The middle bit trap

If $L$ is odd, there is a middle bit $m=\frac{L-1}{2}$. Its output bit is

$b_m=a_m\oplus a_m=0.$

So any valid odd-length palindrome must have middle bit $0$. This kills $8$, because the only reasonable palindrome shape is $0001000$, whose middle bit is $1$. Binary is not here to be vibes-based; the center bit has to behave.

Which leading zeroes can we add?

For $n=0$, the answer is immediately YES: take $x=1$, then $f(x)=1$, so $1\oplus 1=0$.

Now assume $n>0$.

Let the usual binary representation of $n$ be $s$. We are allowed to add leading zeroes because $x$ may have a longer length than $n$.

Suppose we add $p$ leading zeroes. For the padded string to be a palindrome, those $p$ leading zeroes must match the last $p$ bits. Therefore $n$ must have at least $p$ trailing zeroes.

But if we do not remove all trailing zeroes, the remaining inner string would start with $1$ and end with $0$, so it cannot be a palindrome. Therefore $p$ is forced:

$p=\text{number of trailing zeroes of } n.$

So the test becomes very simple:

1. If $n=0$, answer YES.
2. Remove all trailing zeroes from $n$.
3. Check whether the remaining binary string is a palindrome.
4. If its length is odd, its middle bit must be $0$.

If all checks pass, answer YES; otherwise answer NO.

Why this is sufficient

We proved every possible answer must satisfy those conditions. Now we also need to know that the conditions are enough.

Assume the padded bits $b_0,\dots,b_{L-1}$ form a palindrome, and the middle bit is $0$ when $L$ is odd. We can construct bits of $x$ pair by pair.

For each pair $(i,L-1-i)$, we only need

$a_i\oplus a_{L-1-i}=b_i.$

That is always possible: choose one bit freely, then the other is forced. For the outer pair, choose $a_{L-1}=1$ so that $x$ really has length $L$, and set $a_0=1\oplus b_0$. The middle bit, if it exists, requires $b_m=0$, which we already checked.

So the condition is both necessary and sufficient. No hidden nonsense.

Complexity

$n<2^{30}$, so checking bits takes $O(30)$ per test case. With $10^4$ tests, this is tiny.