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

给定两个整数a和b&＃xff0c;我们如何检查b是a的旋转形式&＃xff1f;

例如&＃xff0c;如果我有a &＃61; 0x01020304(在二进制0000 0001 0000 0010 0000 0011 0000 0100中)&＃xff0c;则以下b值正确&＃xff1a;

...

0x4080C1(右旋转2)

0x810182(向右旋转1)

0x2040608(向左旋转1)

0x4080C10(向左旋转2)

...

我想知道是否有解决方案&＃xff0c;除了实际旋转原始值并检查是否匹配。 &＃xff1a;/

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

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

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

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

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

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

在C &＃43;&＃43;中&＃xff0c;不进行字符串转换并假定32位int&＃xff1a;

void test(unsigned a, unsigned b)

{

unsigned long long aa &＃61; a | ((unsigned long long)a<<32);

while(aa>&＃61;b)

{

if (unsigned(aa) &＃61;&＃61; b) return true;

aa>>&＃61;1;

}

return false;

}

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

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

如所述固定。

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

或者只是{...} while(unsigned(aa)&＃xff01;&＃61; a);最多可重复32次&＃xff0c;有时更少。

我认为您必须循环执行(C &＃43;&＃43;)&＃xff1a;

// rotate function

inline int rot(int x, int rot) {

return (x >> rot) | (x <

}

int a &＃61; 0x01020304;

int b &＃61; 0x4080C1;

bool result &＃61; false;

for( int i&＃61;0; i

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

是的&＃xff0c;我的错。

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

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

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

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

听起来很有趣。你可以再详细一点吗&＃xff1f;&＃xff1f;

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

&＃64;MSalters&＃xff1a;有O(N)个旋转和比较&＃xff0c;但每个比较也是O(N)。

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

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

通过在此处得出答案&＃xff0c;以下方法(用C&＃xff03;编写&＃xff0c;但在Java中应类似)将进行检查&＃xff1a;

public static int checkBitRotation(int a, int b) {

string strA &＃61; Convert.ToString(a, 2).PadLeft(32, &＃39;0&＃39;);

string strB &＃61; Convert.ToString(b, 2).PadLeft(32, &＃39;0&＃39;);

return (strA &＃43; strA).IndexOf(strB);

}

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

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

&＃43;1是我从未想到的巧妙技巧。可能比蛮力逼迫慢&＃xff0c;但仍然很整洁。

您可以使用std::bitset<32>::to_string()&＃xff0c;但不多。

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

如果它确实是一个常量&＃xff0c;而不是一个循环常量&＃xff0c;那么还有一些技巧&＃xff1a;

如果a为0或-1&＃xff0c;则不重要

如果a仅设置了1位&＃xff0c;则可以像b !&＃61; 0 && (b & (b - 1)) &＃61;&＃61; 0一样进行测试

如果a设置了2位&＃xff0c;则可以像ror(b, tzcnt(b)) &＃61;&＃61; ror(a, tzcnt(a))那样进行测试

如果a仅具有一组连续的设置位&＃xff0c;则可以使用

int x &＃61; ror(b, tzcnt(b));

int y &＃61; ror(x, tzcnt(~x));

const int a1 &＃61; ror(a, tzcnt(a));     // probably won&＃39;t compile

const int a2 &＃61; ror(a1, tzcnt(~a1));  // but you get the idea

return y &＃61;&＃61; a2;

如果a的许多旋转相同&＃xff0c;则您可以使用它来跳过某些旋转而不是全部测试&＃xff0c;例如&＃xff0c;如果a &＃61;&＃61; 0xAAAAAAAA&＃xff0c;则测试可以是b &＃61;&＃61; a || (b <<1) &＃61;&＃61; a

除了popcnt测试之外&＃xff0c;您还可以比较常数的最小和最大旋转以进行快速的预测试。

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

我会使用Integer.rotateLeft或rotateRight func

static boolean isRotation(int a, int b) {

for(int i &＃61; 0; i <32; i&＃43;&＃43;) {

if (Integer.rotateLeft(a, i) &＃61;&＃61; b) {

return true;

}

}

return false;

}

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

好吧&＃xff0c;另一方面&＃xff0c;b不是a的旋转形式

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

我同意&＃xff0c;这是一个错误&＃xff0c;已修复

输入是a和b&＃xff0c;但是您检查x和y&＃xff1f;

已经将其更改为a和b

我的意思是isRotation(int a&＃xff0c;int b)vs(Integer.rotateLeft(x&＃xff0c;i)&＃61;&＃61; y)