“异或”新手教程与实践
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
“异或”新手教程与实践
时间限制:1s
空间限制:256MB
题目背景
以下内容为异或运算的简单介绍,如果已了解可以跳过。
异或(xor)是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为“xor”。其运算法则为:
如果a、b两个值不相同,则异或结果为 。如果a、b两个值相同,异或结果为 。
异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),这些法则与加法是相同的,只是不带进位,所以异或常被认作不进位加法。
以上是一位二进制的情况,下面考虑多位二进制的情况,称为按位异或(下面的内容以及题面都用 表示按位异或):
按位异或是指将参与运算的两数各个二进位相异或,例如 3 14== = 。
在 C/C++/Python 中, 可以使用 ^ 来计算异或,即可以用 a ^ b 来直接计算 的值。
考虑如下问题:
在非负整数范围内进行考虑,给定一个正整数 ,已知 ,问 的最小值为多少?
将 的二进制表示写出来,可以得到一个 串;对 二进制表示的每一位考虑 和 该位的可能取值:
如果该位为 ,那么 的取值为 或者 ,显然这两种情况的和都是一样的,都为 ;
如果该位为 ,那么 的取值为 或者 ,如果取值是 那么加法会产生进位,为了让加法结果尽可能小,应该选取 ,结果为 .
按以上取值可以发现 的结果和 的结果是一样的,因为加法运算并没有产生进位,所以 的最小值即为 .
题目描述
经过上面的学习,相信你已经很了解异或了,下面来挑战这道题吧:
在非负整数范围内进行考虑,给定两个正整数 和 ,问是否存在一组 使得 ?
你不需要给出 和 的具体值,你只需要判断是否存在即可。
输入格式
第一行一个整数 ,代表测试数据组数。
接下来 行,每行两个整数 和 ,用空格隔开,含义见描述。
输出描述
对于每组测试数据,输出一行判断结果,输出"YES"代表存在对应的 和 的值,否则输出"NO".
样例输入
3
2023 2024
2024 2023
2024 2026
样例输出
NO
NO
YES
样例解释
对于第三组测试数据,我们可以让 ,这样可以满足 .
数据范围与约定
测试点编号 | 每组测试数据约定 | 测试点分值 |
---|---|---|
每个测试点5分 | ||
每个测试点10分 |
对于所有数据,