Beautiful XOR

Let the current value be $a$. In one move we choose some $x$ with $0 \le x \le a$, then replace

$$a \leftarrow a \oplus x.$$

The whole problem is about the numeric restriction $x \le a$. XOR itself is easy; the constraint is where the trap lives.

The Main Invariant

Look at the highest set bit of $a$.

If the highest set bit of $a$ is at position $k$, then $a < 2^{k+1}$. Since $x \le a$, we also have $x < 2^{k+1}$, so $x$ has no bit above position $k$.

Therefore $a \oplus x$ also cannot have any bit above position $k$.

So the highest set bit can stay the same or go down, but it can never go up. No magic, no loophole, no XOR wizardry. If $b$ has a higher set bit than the initial $a$, the answer is impossible.

Formally, if

$$\operatorname{msb}(b) > \operatorname{msb}(a),$$

print $-1$.

Now Show Everything Else Is Possible

Let

$$p = 2^{\operatorname{msb}(a)},$$

so $p$ is the highest power of two not exceeding the initial $a$.

There are two useful cases.

Case 1: $a$ and $b$ have the same highest bit

Then both numbers contain bit $p$.

So in $a \oplus b$, that bit cancels out. This means

$$a \oplus b < p.$$

And since $p \le a$, we get

$$a \oplus b < p \le a.$$

So the direct move works:

$$x = a \oplus b.$$

Then

$$a \oplus x = a \oplus (a \oplus b)=b.$$

One operation. Clean.

Case 2: $b$ has a smaller highest bit

Directly using $x=a\oplus b$ might fail because it can be larger than $a$. Example-style nonsense happens here.

Instead, first turn $a$ into the all-ones number with the same highest bit:

$$M = 2p - 1.$$

This number looks like

$$111\ldots111_2$$

from bit $0$ through the highest bit of $a$.

Can we move from $a$ to $M$ in one operation? Yes. Choose

$$x_1 = a \oplus M.$$

Since $a$ and $M$ both have the highest bit $p$, that bit cancels in $x_1$, so

$$x_1 < p \le a.$$

Thus the move is legal, and after it we have $a=M$.

Now move from $M$ to $b$. Choose

$$x_2 = M \oplus b.$$

Because $b < p$ in this case, and $M$ has the highest bit $p$, the value $M\oplus b$ still has highest bit $p$, but it is not equal to $M$ unless $b=0$. Since the constraints have $b\ge1$, we get

$$x_2 < M.$$

So $x_2 \le M$, meaning the second move is legal.

Then

$$M \oplus x_2 = M \oplus (M \oplus b)=b.$$

So two operations always suffice.

Construction Summary

For each test case:

• If $a=b$, print $0$.
• If $b$ has a higher highest bit than $a$, print $-1$.
• Otherwise, if $a\oplus b \le a$, print one move: $a\oplus b$.
• Otherwise, let $M=2p-1$, where $p$ is the highest power of two not exceeding $a$. Print two moves:

$$(a\oplus M),\quad (M\oplus b).$$

This uses at most $2$ operations, way below the limit of $100$. The limit is basically there for vibes.

Correctness Proof

We prove the algorithm prints a valid answer exactly when one exists.

First, suppose $b$ has a higher highest set bit than the initial $a$. During any operation, $x\le a$, so $x$ has no bit above the highest set bit of $a$. Therefore $a\oplus x$ also has no bit above that position. Thus the highest set bit can never increase. So reaching such a $b$ is impossible, and printing $-1$ is correct.

Now suppose $b$ does not have a higher highest set bit than $a$.

If $a=b$, zero operations are valid.

If $a\oplus b\le a$, choosing $x=a\oplus b$ is legal, and the new value becomes $a\oplus(a\oplus b)=b$. So the one-operation output is valid.

Otherwise, define $p$ as the highest power of two not exceeding $a$, and define $M=2p-1$.

The first printed value is $x_1=a\oplus M$. Since $a$ and $M$ share the same highest bit $p$, that bit is not set in $x_1$, so $x_1<p\le a$. Hence the first operation is legal and changes $a$ to $M$.

The second printed value is $x_2=M\oplus b$. Since $b$ has no bit above the highest bit of $M$, this XOR also has no bit above it. Also, because $b\ge1$, at least one low bit of $M$ is flipped from $1$ to $0$, so $x_2<M$. Hence $x_2\le M$, and the second operation is legal. It changes $M$ to $M\oplus(M\oplus b)=b$.

Thus whenever the algorithm does not print $-1$, its sequence is legal and reaches $b$. Combined with the impossibility argument, the algorithm is correct.

Complexity

Each test case does only a constant amount of bit work.

$$O(1)$$

time per test case, and $O(1)$ extra memory.