java整数个位十位对调_关于java：检查整数是另一个整数的位旋转

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

例如，如果我有a = 0x01020304(在二进制0000 0001 0000 0010 0000 0011 0000 0100中)，则以下b值正确：

...

0x4080C1(右旋转2)

0x810182(向右旋转1)

0x2040608(向左旋转1)

0x4080C10(向左旋转2)

...

我想知道是否有解决方案，除了实际旋转原始值并检查是否匹配。 ：/

仅32次循环(您的情况下为32位)并检查是否匹配。

我不知道这在多大程度上有助于加快速度，但是您可以尝试使用POPCNT内在函数分别计算a和b的位数。 如果数字不同，答案必须为false。 否则，请对所有可能的旋转进行全面检查。

这很困难，因为旋转不是算术运算，而不是移位(移位是除以2的幂)

我仍然在等待有人发布基于多项式除法的答案:)

如果cpu实现了该指令，则弹出计数可能是有用的优化，如果2个数字中的1个数字不匹配，则立即中断

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

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

}

看来这是最好的答案。稍作更新以在参数中包含b。谢谢

只是一些小注释：(1)应该是unsigned long long，不是吗？ (2)移位表达式的类型是左操作数的类型，因此您应该将其中的a强制转换为unsigned long long，仅使用32LL是不够的。

如所述固定。

您最终可以测试if(unsigned(aa)== a)返回false；由于对称性，一些数字的旋转数少于32，例如0xAAAAAAAA，尽管我不知道它在统计上是否会加快或减慢

或者只是{...} while(unsigned(aa)！= a);最多可重复32次，有时更少。

我认为您必须循环执行(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;

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

是的，我的错。

所有Id的拳头宁愿使用unsigned int进行任何合理的位操作，然后CHAR_BIT比8(或者只是std::numeric_limits::digits而不是整个sizeof疯狂)更适合一些，但是好的，那些只是微小的缺陷。通常，这可能仍然是最好的方法。

在一般情况下(假定任意长度的整数)，组成每次旋转的天真解是O(n ^ 2)。

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

尽管这对于长度为32的整数没有太大帮助。

听起来很有趣。你可以再详细一点吗？？

但是，这是错误的：考虑到每次旋转仅O(N)。您旋转a来匹配b，但是b本身没有旋转。

@MSalters：有O(N)个旋转和比较，但每个比较也是O(N)。

我认为这是谈论复杂性没有用的情况之一。如果问题是关于BigIntegers，我将支持您。但是在这种情况下，CPU不会逐位比较，因此O(N ^ 2)似乎对我有些误导。

@HonzaBrabec：我明白您的意思了，但是我之所以发布此一般性答复，是因为OP专门说了"整数"而不是" ints"；我可能对此已经读得太多了...

通过在此处得出答案，以下方法(用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的旋转版本。

嗯，在将整个对象转换成字符串并进行字符串搜索之前，我宁愿执行32次简单的整数移位循环。

+1是我从未想到的巧妙技巧。可能比蛮力逼迫慢，但仍然很整洁。

您可以使用std::bitset<32>::to_string()，但不多。

如果a或b是常数(或循环常数)，则可以预先计算所有旋转并将其排序，然后使用非常数作为键进行二进制搜索。那是更少的步骤，但是这些步骤在实践中比较慢(二进制搜索通常是通过预测错误的分支来实现的)，因此可能不会更好。

如果它确实是一个常量，而不是一个循环常量，那么还有一些技巧：

如果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测试之外，您还可以比较常数的最小和最大旋转以进行快速的预测试。

当然，正如我在一开始所说的，当a和b都是变量时，这都不适用。

我会使用Integer.rotateLeft或rotateRight func

static boolean isRotation(int a, int b) {

for(int i = 0; i < 32; i++) {

if (Integer.rotateLeft(a, i) == b) {

return true;

}

}

return false;

}

您只需要在32个可能的值中进行30个测试。尽管x == y是否表示没有旋转是有争议的，但您仍然缺少至少一种情况。

好吧，另一方面，b不是a的旋转形式

这就是为什么我说这是有争议的。但是，即使您认为第0(也就是第32)旋转应返回false，您仍然会错过第31旋转。

我同意，这是一个错误，已修复

输入是a和b，但是您检查x和y？

已经将其更改为a和b

我的意思是isRotation(int a，int b)vs(Integer.rotateLeft(x，i)== y)