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

Question

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

例如，如果我有a = 0x01020304（二进制表示为0000 0001 0000 0010 0000 0011 0000 0100），则下列的b值是正确的：

• ...
• 0x4080C1（向右旋转2位）
• 0x810182（向右旋转1位）
• 0x2040608（向左旋转1位）
• 0x4080C10（向左旋转2位）
• ...

- user2462322

---

除了实际旋转原始值并检查是否匹配之外，我想知道是否有其他解决方案。 :/ - Peter Jaloveczki

只需循环32次（在您的情况下是32位），并检查是否匹配。 - Boris

我不知道这会对加速有多少帮助，但你可以尝试使用POPCNT编译器内置函数来分别计算a和b的位数。如果这些数字不同，则答案必须为“false”。否则，您需要进行所有可能的旋转的完整检查。 - jogojapan

这很难，因为旋转不是数学运算，不像移位（它是乘以或除以二的幂）。 - MSalters

我还在等待有人基于多项式除法发表答案 :) - avakar

如果CPU实现了pop count指令，那么它可能是一个有用的优化，即如果两个数字中的1的数量不匹配，立即中断。 - NoSenseEtAl

Answer 1

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

- Quimey

Answer 2

在C++中，假设int为32位且没有字符串转换：

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;
}

- MSalters

---

看起来这个是最好的答案。稍微更新一下，将 b 包含在参数中。谢谢。 - user2462322

只是一些小注：(1) 应该是unsigned long long，对吗？(2) 位移表达式的类型与左操作数相同，所以你应该将其中的a强制转换为unsigned long long，仅仅使用32LL是不够的。 - Christian Rau

你最终可以测试if(unsigned(aa)==a) return false; 因为对称性，有些数字少于32个不同的旋转，比如0xAAAAAAAA，虽然我不知道它是否会在统计上加快或减慢。 - aka.nice

或者只需执行 {...} while( unsigned(aa)!=a); 它最多迭代32次，有时会更少。 - aka.nice

Answer 3

我认为你需要在一个循环中完成它（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;

- WoJo

---

不适用于相同的a和b。您应该从i = 0开始循环。 - Boris

首先，对于任何合理的位操作，我更喜欢使用无符号整数而不是有符号整数。然后，“CHAR_BIT”比“8”更适合（或者只需使用“std::numeric_limits<unsigned int>::digits”，而不是整个“sizeof”混乱）。但是，这些只是小缺陷。总体而言，这可能仍然是最佳方法。 - Christian Rau

Answer 4

在一般情况下（假设整数长度任意），每个旋转都包含的朴素解决方案是 O(n^2)。

但实际上你正在进行相关操作。通过使用 FFT 在频域中进行相关操作可以在 O(n log n) 时间内完成。

这对于长度为 32 的整数帮助不大。

- Oliver Charlesworth

---

听起来很有趣。你能具体说明一下吗？ - Sungmin

然而，这是错误的：考虑到每个旋转仅为O（N）。您会旋转一个以匹配b，但是b本身并没有旋转。 - MSalters

@MSalters：有O(N)次旋转和比较，但每次比较也是O(N)。 - Oliver Charlesworth

我认为在讨论复杂性方面，这是其中一种无用的情况。如果问题涉及BigIntegers，我会支持你的观点。然而，在这种情况下，CPU并不是逐位比较，因此O（N^2）对我来说有些误导性。 - Honza Brabec

@HonzaBrabec：我明白你的意思，但我发表这个一般性回复的原因是因为OP明确说了“整数”，而不是“ints”；不过我可能读多了…… - Oliver Charlesworth

Answer 5

通过在这里获取答案，下面的方法（用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的旋转版本。

- David

---

在将整个东西转换为字符串并进行字符串搜索之前，我宁愿执行简单的整数位移循环32次。 - Christian Rau

+1 个好技巧，我想不到。可能比暴力破解慢，但仍然很棒。 - Retired Ninja

你可以使用 std::bitset<32>::to_string()，没什么难度。 - TemplateRex

Answer 6

如果a或b是常量（或循环常量），您可以预先计算所有旋转并对其进行排序，然后使用不是常量的那个作为关键字进行二分查找。这样步骤会更少，但实际上步骤会变慢（二分查找通常使用预测不良的分支实现），因此可能不是更好的选择。

在它确实是一个常量而不是循环常量的情况下，还有一些技巧：

• 如果 a 是 0 或 -1，则很简单
• 如果 a 只有一个比特位被设置，您可以使用以下测试 b != 0 && (b & (b - 1)) == 0
• 如果 a 有两个比特位被设置，您可以使用以下测试 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 测试之外。

当然，就像我一开始所说的那样，在a和b均为变量时，上述内容都不适用。

- harold

Answer 7

我会使用 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;
}

- Evgeniy Dorofeev

---

你只进行了30个测试，而不是32个可能的值。虽然x == y是否意味着没有旋转还有争议，但你仍然至少缺少一个情况。 - syam

好的，另一方面，b不是a的旋转版本。 - Evgeniy Dorofeev

这就是为什么我说这是有争议的。但是即使您认为第0（又称第32）次旋转应返回false，您仍然错过了第31次旋转。 - syam

我同意，那是个 bug，已经修复了。 - Evgeniy Dorofeev

输入是a和b，但你检查的是x和y？ - David

我的意思是 isRotation(int a, int b) 和 (Integer.rotateLeft(x, i) == y) 的区别。 - David