检查整数是另一个整数的位旋转

Question

给定两个整数a和b,我们如何检查b是旋转版本？

例如,如果我a = 0x01020304(二进制0000 0001 0000 0010 0000 0011 0000 0100),则以下b值是正确的:

• ...
• 0x4080C1 (右旋2)
• 0x810182 (右旋1)
• 0x2040608 (左转1)
• 0x4080C10 (左转2)
• ...

Answer 1

对于n位数,您可以使用KMP算法在复杂度为O(n)的两个副本中搜索b.

Answer 2

在C++中,没有字符串转换并假设32位int:

void test(unsigned a, unsigned b)
{
  unsigned long long aa = a | ((unsigned long long)a<<32);
  while(aa>=b)
  {
    if (unsigned(aa) == b) return true;
    aa>>=1;
  }
return false;
}