给定两个整数a和b,我们如何检查b是a的旋转版本?
例如,如果我有a = 0x01020304
(二进制表示为0000 0001 0000 0010 0000 0011 0000 0100
),则下列的b值是正确的:
- ...
0x4080C1
(向右旋转2位)0x810182
(向右旋转1位)0x2040608
(向左旋转1位)0x4080C10
(向左旋转2位)- ...
给定两个整数a和b,我们如何检查b是a的旋转版本?
例如,如果我有a = 0x01020304
(二进制表示为0000 0001 0000 0010 0000 0011 0000 0100
),则下列的b值是正确的:
0x4080C1
(向右旋转2位)0x810182
(向右旋转1位)0x2040608
(向左旋转1位)0x4080C10
(向左旋转2位)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;
}
unsigned long long
,对吗?(2) 位移表达式的类型与左操作数相同,所以你应该将其中的a
强制转换为unsigned long long
,仅仅使用32LL
是不够的。 - Christian Rau我认为你需要在一个循环中完成它(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;
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);
}
std::bitset<32>::to_string()
,没什么难度。 - TemplateRexa
或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
均为变量时,上述内容都不适用。我会使用 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;
}
x == y
是否意味着没有旋转还有争议,但你仍然至少缺少一个情况。 - syam
a
和b
的位数。如果这些数字不同,则答案必须为“false”。否则,您需要进行所有可能的旋转的完整检查。 - jogojapan