C. 小陶的位运算挑战

    传统题 1000ms 256MiB

小陶的位运算挑战

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景:

在桃花山下的桃花观里,活了一千年的长生者陶眠正在研究他的“共享修炼长生系统”。为了在云共享中永远比他的卷王徒弟们高出一筹,系统面板弹出了两个被加密的底层参数 xxyy

若要完美触发被动效果,小陶道长需要找到一个“平衡因子” nn。通过按位异或(XOR)运算改变这两个参数的二进制分布,使得变换后 xx 的二进制中 11 的个数,popcount)严格大于变换后的 yy 的二进制中 11 的个数。

题目描述:

给定两个非负整数 xxyy,你需要构造一个整数 n0n<231n(0 \le n < 2^{31}),使得:

$$\operatorname{popcount}(x \oplus n) > \operatorname{popcount}(y \oplus n)$$

其中 popcount(z)\operatorname{popcount}(z) 表示 zz 在二进制表示中 11 的个数。例如 popcount(3)=2\operatorname{popcount}(3) = 2(二进制为 1111),popcount(4)=1\operatorname{popcount}(4) = 1(二进制为 100100)。

\oplus 表示按位异或运算。

题目保证在给定范围内一定有解。如果有多解,输出任意一个满足条件的 nn 即可。

输入格式:

第一行一个整数 T1T106T(1 \le T \le 10^6),表示测试数据组数。

接下来 TT 行,每行两个整数 x,y0x<y<231x, y(0 \le x < y < 2^{31})

输出格式:

对于每组数据,输出一行一个整数 nn,满足上述不等式。

输入样例:

2
1 2
0 4

输出样例:

2
4

说明/提示:

本题数据量较大,请使用较快的读入方式。

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

cout << "答案" << '\n';

金陵科技学院算法暑假集训阶段水平测试Ⅰ

未参加
状态
已结束
规则
XCPC
题目
9
开始于
2026-7-9 13:15
结束于
2026-7-9 17:15
持续时间
4 小时
主持人
参赛人数
7