Mikasa
Contest: Codeforces Round 735 (Div. 2)
Difficulty rating: 1800
Tags: binary search, bitmasks, greedy, implementation

You are given two integers $$$n$$$ and $$$m$$$. Find the $$$\operatorname{MEX}$$$ of the sequence $$$n \oplus 0, n \oplus 1, \ldots, n \oplus m$$$. Here, $$$\oplus$$$ is the bitwise XOR operator.

$$$\operatorname{MEX}$$$ of the sequence of non-negative integers is the smallest non-negative integer that doesn't appear in this sequence. For example, $$$\operatorname{MEX}(0, 1, 2, 4) = 3$$$, and $$$\operatorname{MEX}(1, 2021) = 0$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 30\,000$$$)  — the number of test cases.

The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n, m \le 10^9$$$).

Output format:
For each test case, print a single integer  — the answer to the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2, 3 \oplus 3, 3 \oplus 4, 3 \oplus 5$$$, or $$$3, 2, 1, 0, 7, 6$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$4$$$.

In the second test case, the sequence is $$$4 \oplus 0, 4 \oplus 1, 4 \oplus 2, 4 \oplus 3, 4 \oplus 4, 4 \oplus 5, 4 \oplus 6$$$, or $$$4, 5, 6, 7, 0, 1, 2$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$3$$$.

In the third test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2$$$, or $$$3, 2, 1$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$0$$$.

Example input:
5
3 5
4 6
3 2
69 696
123456 654321

Example output:
4
3
0
640
530866

Editorial:
How can we check if $$$k$$$ is present in the sequence $$$n\oplus 0,n\oplus 1,...,n\oplus m$$$ ? Think.
If $$$k$$$ is present in the sequence, then there must be some $$$x$$$ such that $$$0 \le x \le m$$$ and $$$n\oplus x = k$$$, right?
Did you know that $$$n\oplus k = x$$$ is equivalent to $$$n\oplus x = k$$$ ?
So we can just check if $$$n\oplus k \le m$$$ or not! Pretty simple!
So the modified problem is to find the smallest non-negative integer $$$k$$$ such that $$$n\oplus k \ge m+1$$$. Can you solve it now?
Think using bits.
Let $$$p = m+1$$$ and $$$t_i$$$ be the $$$i$$$-th bit of $$$t$$$. We will find the smallest $$$k$$$ such that $$$n\oplus k \ge p$$$.
Let's build $$$k$$$ greedily from the highest bit to the lowest bit. Let's say we will find the $$$i$$$-th bit of $$$k$$$ and the higher bits have already been generated. Obviously, we will try to make this bit off if possible. When will it be impossible? Think.
If $$$n_i = p_i$$$, we can set $$$k_i = 0$$$ as $$$n_i \oplus 0 = n_i \ge p_i$$$. If $$$n_i = 1$$$ and $$$p_i = 0$$$, we can break here by setting the remaining bits of $$$k$$$ off as no matter what the remaining bits of $$$n$$$ are, $$$n \oplus k$$$ will always be greater than $$$p$$$. Finally, if $$$n_i = 0$$$ and $$$p_i = 1$$$, we must set $$$k_i = 1$$$, as we have no other options.
Check my solution for more clarity.
Time Complexity: $$$\mathcal{O}(log(n))$$$ per test case.