给定两个整数 x,y ,构造一个整数 n 使得 x⊕n>y⊕n.
保证数据一定存在一个合法解。
【名词解释】
⊕:指位运算中的按位异或(Bitwise XOR),对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识,可以参考 OI-Wiki的相关章节。
本题答案不唯一,只要满足题目条件即可。
核心原理:异或运算特性为相同位得 0,不同位得 1。令 k=x⊕y,则 k 中二进制为 1 的位,就是 x 与 y 不相同的位。
只要让 n 在这一最高不同位设为 1,低位任意取值,就能保证x⊕n 该位为 1、y⊕n 该位为 0,满足大小关系。
解题思路:用__builtin_clzll求出 k 最高位位置,将 1 左移该位数,构造出仅最高不同位为 1 的数,即为合法答案。该做法时间复杂度 \(O(1)\),可高效处理多组询问。
#include <iostream>
#define ll long long
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll T;
cin >> T;
while (T--) {
ll x, y;
cin >> x >> y;
ll k = x ^ y;
ll mask = 1LL << (31 - __builtin_clz((unsigned int)k));
cout << mask << endl;
}
return 0;
}

京公网安备 11010502036488号