XOR Sequences
Contest: Codeforces Round 951 (Div. 2)
Difficulty rating: 1000
Tags: bitmasks, greedy

You are given two distinct non-negative integers $$$x$$$ and $$$y$$$. Consider two infinite sequences $$$a_1, a_2, a_3, \ldots$$$ and $$$b_1, b_2, b_3, \ldots$$$, where

- $$$a_n = n \oplus x$$$;
- $$$b_n = n \oplus y$$$.

Here, $$$x \oplus y$$$ denotes the bitwise XOR operation of integers $$$x$$$ and $$$y$$$.

For example, with $$$x = 6$$$, the first $$$8$$$ elements of sequence $$$a$$$ will look as follows: $$$[7, 4, 5, 2, 3, 0, 1, 14, \ldots]$$$. Note that the indices of elements start with $$$1$$$.

Your task is to find the length of the longest common subsegment$$$^\dagger$$$ of sequences $$$a$$$ and $$$b$$$. In other words, find the maximum integer $$$m$$$ such that $$$a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$$$ for some $$$i, j \ge 1$$$.

$$$^\dagger$$$A subsegment of sequence $$$p$$$ is a sequence $$$p_l,p_{l+1},\ldots,p_r$$$, where $$$1 \le l \le r$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9, x \neq y$$$) — the parameters of the sequences.

Output format:
For each test case, output a single integer — the length of the longest common subsegment.

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

Note:
In the first test case, the first $$$7$$$ elements of sequences $$$a$$$ and $$$b$$$ are as follows:

$$$a = [1, 2, 3, 4, 5, 6, 7,\ldots]$$$

$$$b = [0, 3, 2, 5, 4, 7, 6,\ldots]$$$

It can be shown that there isn't a positive integer $$$k$$$ such that the sequence $$$[k, k + 1]$$$ occurs in $$$b$$$ as a subsegment. So the answer is $$$1$$$.

In the third test case, the first $$$20$$$ elements of sequences $$$a$$$ and $$$b$$$ are as follows:

$$$a = [56, 59, 58, 61, 60, 63, 62, 49, 48, 51, 50, 53, 52, 55, 54, \textbf{41, 40, 43, 42}, 45, \ldots]$$$

$$$b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \ldots]$$$

It can be shown that one of the longest common subsegments is the subsegment $$$[41, 40, 43, 42]$$$ with a length of $$$4$$$.

Example input:
4
0 1
12 4
57 37
316560849 14570961

Example output:
1
8
4
33554432

Editorial:
Consider two numbers $$$v$$$ and $$$u$$$ such that $$$x \oplus v = y \oplus u$$$. Then consider the numbers $$$x \oplus (v + 1)$$$ and $$$y \oplus (u + 1)$$$. Let's look at the last bit of $$$v$$$ and $$$u$$$. Possible scenarios:
• Both bits are equal to $$$0$$$ — adding one will change the bits at the same positions, therefore $$$x \oplus (v + 1) = y \oplus (u + 1)$$$;
• Both bits are equal to $$$1$$$ — adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit;
• Bits are different — adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that $$$x \oplus (v + 1) \neq y \oplus (u + 1)$$$.
It is clear that we need to maximize the number of zeros in the maximum matching suffix of $$$u$$$ and $$$v$$$. Obviously, this number is equal to the maximum matching suffix of $$$x$$$ and $$$y$$$. Let $$$k$$$ be the length of the maximum matching suffix of $$$x$$$ and $$$y$$$, then the answer is $$$2^k$$$.
This can be calculated in $$$O(\log C)$$$ time for one test case, where $$$C$$$ is the limit on $$$x$$$ and $$$y$$$.