题解 | 最长异或公共子段

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//题目要求连续的一段 所以我们的ai和bi改变时 只能在二进制的最低位上进行+1 
//已知有这样的限制 我们又能自然的想到 我们可以找出x和y的二进制中最长的连续相同的一段（并且位要对齐）
//对于这一段 我们可以构造出对应的ai和bi异或上去 使其他位无效 然后剩下这一段的值相等
//例如 100110 和 100111 10011是他们最长的公共段 我们构造出两个数 这两个数只有最低位不一样
//例如 011001 和 011000 这样我们异或上去 会发现得到一个相同的数 但是问题来了 我们要向后移
//动这两个数时 为了连续 需要在最低位+1 这个时候我们就会发现 移动后的数 再分别异或 得到的结果就不一样了
//因此 我们可以发现 我们需要从最低位起 取x和y相同的一段 这样 我们在改变构造出的ai和bi时 在一定的范围对他们+1然后异或 依然能得到相同的值
//例如 001101和 111101 从最低位开始有四位相同 于是我们可以构造出a:11xxxx b:00xxxx 对这样的a和b执行加一然后分别异或x和y 得到的结果依然相同 范围即x和y二进制相同段的长度
//求长度我们可以用位运算技巧(x^y)&(-(x^y))来找出x和y第一个不同的1所处的位置的2的幂 即为答案
	int x,y;
    cin >> x >> y;
    cout << ((x^y)&(-(x^y))) << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}