这是一篇题解 | x_to_y_2

·首先理解一下题意，给定整数x和y，可以对x进行整除2操作或 | 上任意一个整数z，求经过最少多少次操作能将x变为y。

·首先对 | z 操作我们不难知道

如果x和y不相等的情况下，x已经没有“x有而y没有”的数位时（如图）

那显然可以一步，完成

·可是如果有“x有而y没有” 那 | z 本身只能 把0变成1、不能把1变成0

·所以这种位就只能用 整除2 消掉（相当于整体右移一位）

·所以只要，一直右移到，x没有“x有而y没有” 的位的时候就行了

·判断 “x有而y没有”可以用 (x | y) != y （因为位运算的优先级问题，这里一定要代括号）

·还有就是因为x右移到0时肯定满足，所以不用专门判断x != 0

		while((x | y) != y)
		{
			x >>= 1;
			ans ++ ;
		}

·然后注意，如果移位完后x和y相等，此时是不需要 | z的

		if (x != y) ans ++ ; // | z
		printf("%d\n", ans);

·时间复杂度为O(Tlogx)

·完整代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

ll x, y; 
int ans = 0;

int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{
		scanf("%lld%lld", &x, &y);
		ans = 0;
		while((x | y) != y)
		{
			x >>= 1;
			ans ++ ;
		}
		if (x != y) ans ++ ;
		printf("%d\n", ans);
	}
}

·希望对大家有所帮助qwq.