C++程序检查两个数字是否是彼此的位旋转

给定两个正整数x和y，检查一个整数是否是通过旋转另一个整数的位得到的。

输入限制： 0 < x，y < 2^32

位旋转： 旋转（或循环移位）是类似于移位的操作，但是一个端掉落的位被放回到另一端。

有关位旋转的更多信息，请参见 here。

示例1：

输入：a = 8，b = 1

输出：是的

说明。

a的表示方法= 8：0000 0000 0000 0000 0000 0000 0000 1000

b的表示方法=1：0000 0000 0000 0000 0000 0000 0000 0001

如果我们将a向右旋转3个单位，则会得到b，因此答案是yes

示例2：

输入：a = 122， b = 2147483678

输出：是的

说明

a的表示方法= 122：0000 0000 0000 0000 0000 0000 0111 1010

b的表示方法= 2147483678：1000 0000 0000 0000 0000 0000 0001 1110

如果我们将a向右旋转2个单位，则会得到b，因此答案是yes

由于x或y可以表示的总位数为32，因为x，y>0且x，y<2^32。

因此，我们需要找到x的所有32个可能的旋转并将其与y进行比较，直到x和y不相等为止。

为此，我们使用具有64位的临时变量x64，它是x与x相连接的结果即：

x64具有首32位与x的位相同，最后32位与x64的位相同。

然后，我们将x64不断向右移动1个单位，并将x64的最右边的32位与y进行比较。

以这种方式，我们将能够获取由于旋转而产生的所有可能的位组合。

下面是上述算法的实现。

// C++ program to check if two numbers are bit rotations
// of each other.
#include <iostream>
using namespace std;
 
// function to check if  two numbers are equal
// after bit rotation
bool isRotation(unsigned int x, unsigned int y)
{
    // x64 has concatenation of x with itself.
    unsigned long long int x64 = x | ((unsigned long long int)x << 32);
 
    while (x64 >= y)
    {
        // comparing only last 32 bits
        if (unsigned(x64) == y)
            return true;
 
        // right shift by 1 unit
        x64 >>= 1;
    }
    returnfalse;
}
 
// driver code to test above function
int main()
{
    unsigned int x = 122;
    unsigned int y = 2147483678;
 
    if (isRotation(x, y))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
 
    return 0;
}

输出