牛客练习赛130-A题题解

题目描述如下:

给定两个整数 x,y，jackle 希望把 x 变成 y。

他每次可以进行如下两种操作之一：

• 选择任意一个整数 z，令 x=x&z。
• 选择任意一个整数z，令x=x|z。

请问最少操作几次可以把 x 变成 y。

输入描述:

本题有多组测试数据。

第一行输入 1个正整数 T(1≤T≤10^5) ，表示数据组数。

接下来 T 行，每行 2 个整数 x,y(0≤x,y≤10^18)。

输出描述:

对于每组测试数据，输出最少操作次数。

示例

输入
2
0 0
0 1

输出
0
1

解题思路:

我们阅读题面可以发现，看到”最少操作次数“这样的描述，我们就可以看出来这是一道贪心的思维题。

那我们先思考一下，我们先看x和y的范围是0到10^18,因此我们要给x，y开long long，这里的输入输出并没有很多，所以用不着快读。

接下来，我们想想，题目给我们限制了两种操作方式，一个是位与"&"操作，一个是位或"|"操作，那么当x==y的时候，我们直接输出0就可以。

若x!=y,我们如果想把x变成y，是不是只需要先让x=x&0,在让x=x|y,就可以了。比如: 2=0010,5=0101,我们首先将2=2&0，2就变成了0，0=0|5，0就变成了5，所以最多只需要2步即可。

到这就完了?还没有，我们还需要考虑1的情况，比如说2=0010，3=0011，他们只有一位不同,那么2=3，是不是只需要让2=2|3就可以了，也就是只需要1步。那我们如何思考这个判断条件呢？

第一个例子，p=x&y,x=2,y=3,

p=2&3,0010&0011=0010,所以p=2=x。

第二个例子，p=x&y,x=11,y=10,

p=11&10,1011&1010=1010,.p=10=y

你发现了什么？是不是只要判断x&y等于x或者x&y等于y，就能知道是不是只需要1步了?

AC代码如下:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int t;
int main()
{
    cin>>t;
    
    while(t--){
        ll x,y;
        cin>>x>>y;
        
        ll p;
		
		p=x&y;
		
		if(x==y){
			cout<<0<<endl;
		}else if(p==x||p==y){
			cout<<1<<endl;
		}else{
			cout<<2<<endl;
		}
		
    }

    
    
}