欢迎访问==> 【考研OR保研】机试题
题目描述
给出两个不大于 $65535$ 的非负整数,判断其中一个的 $16$ 位二进制表示形式,是否能由另一个的 $16$ 位二进制表示形式经过循环左移若干位而得到。
循环左移和普通左移的区别在于:最左边的那一位经过循环左移一位后就会被移到最右边去。
比如: 1011 0000 0000 0001
经过循环左移一位后,变成 0110 0000 0000 0011
,若是循环左移2位,则变成 1100 0000 0000 0110
。
输入格式
输入包含多组测试数据。
每组数据包含两个整数,占一行。
输出格式
每组数据输出一个结果,如果两个数之间能够进行移位转化则输出 YES
,否则输出 NO
。
数据范围
输入整数不超过 $65535$。
输入最多包含 $100$ 组数据。
输入样例:
2 4
9 18
45057 49158
7 12
输出样例:
YES
YES
YES
NO
C++ 代码
/*
知识积累:
【n >> i & 1】可以判断n的二进制表示中第i位是0还是1
判断两个串s和t其中一个能否通过另一个循环移位得到,
可以将s串伸长,s = s + s, 判断伸长后的s串中是否包含t串即可
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
while(cin >> a >> b)
{
string x, y;
for(int i = 0; i < 16; i ++)
{
x = x + to_string(a >> i & 1); //x表示a的二进制表示
y = y + to_string(b >> i & 1); //y表示b的二进制表示
}
y += y;
if(y.find(x) != -1) puts("YES");
else puts("NO");
}
return 0;
}