12

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

例如，如果我有a = 0x01020304（二进制0000 0001 0000 0010 0000 0011 0000 0100），那么以下 b 值是正确的：

  • ...
  • 0x4080C1（右旋2）
  • 0x810182（右旋1）
  • 0x2040608（左旋1）
  • 0x4080C10（左旋2）
  • ...
4

7 回答 7

6

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

于 2013-06-07T11:36:37.953 回答
5

在 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;
}
于 2013-06-07T10:58:56.113 回答
4

我认为您必须循环执行（c ++）：

// rotate function
inline int rot(int x, int rot) {
   return (x >> rot) | (x << sizeof(int)*8 - rot));
}

int a = 0x01020304;
int b = 0x4080C1;
bool result = false;

for( int i=0; i < sizeof(int)*8 && !result; i++) if(a == rot(b,i)) result = true;
于 2013-06-07T08:48:52.313 回答
3

在一般情况下（假设任意长度的整数），组成每个旋转的简单解决方案是 O(n^2)。

但是你实际上在做的是一种相关性。您可以通过使用 FFT 通过频域在 O(n log n) 时间内进行相关性。

不过，这对长度为 32 的整数没有多大帮助。

于 2013-06-07T09:01:25.040 回答
1

通过在此处导出答案，以下方法（用 C# 编写，但在 Java 中应类似）将进行检查：

public static int checkBitRotation(int a, int b) {
    string strA = Convert.ToString(a, 2).PadLeft(32, '0');
    string strB = Convert.ToString(b, 2).PadLeft(32, '0');
    return (strA + strA).IndexOf(strB);
}

如果返回值为 -1，则 b 不是 a 的旋转版本。否则，b 是 a 的旋转版本。

于 2013-06-07T08:59:54.123 回答
1

如果aorb是一个常数（或循环常数），您可以预先计算所有旋转并对它们进行排序，然后使用不是常数的一个作为键进行二分搜索。那是更少的步骤，但在实践中步骤更慢（二进制搜索通常使用预测错误的分支来实现），所以它可能不会更好。

如果它真的是一个常数，而不是一个循环常数，还有一些技巧：

  • 如果a是 0 或 -1，它是微不足道的
  • 如果a只设置了 1 位，您可以像这样进行测试b != 0 && (b & (b - 1)) == 0
  • 如果a设置了 2 位，您可以像这样进行测试ror(b, tzcnt(b)) == ror(a, tzcnt(a))

  • 如果a只有一组连续的设置位，您可以使用

    int x = ror(b, tzcnt(b));
int y = ror(x, tzcnt(~x));
const int a1 = ror(a, tzcnt(a));     // probably won't compile
const int a2 = ror(a1, tzcnt(~a1));  // but you get the idea
return y == a2;
  • 如果 的许多旋转a是相同的，您可以使用它来跳过某些旋转而不是全部测试，例如，如果a == 0xAAAAAAAA，测试可以是b == a || (b << 1) == a
  • 除了测试之外，您还可以比较常数的最小和最大旋转以进行快速预popcnt测试。

当然，正如我在开始时所说，这都不适用 whena和bare both variables。

于 2013-06-07T22:14:45.320 回答
0

我会使用Integer.rotateLeft或rotateRight功能

static boolean isRotation(int a, int b) {
    for(int i = 0; i < 32; i++) {
        if (Integer.rotateLeft(a, i) == b) {
            return true;
        }
    }
    return false;
}
于 2013-06-07T08:48:19.277 回答