12

2 つの整数 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 の 2 つのコピー内で b を検索できます。

于 2013-06-07T11:36:37.953 に答える
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

aorが定数 (またはループ定数) の場合b、すべての回転を事前に計算して並べ替え、定数ではないものをキーとしてバイナリ検索を実行できます。これはステップ数が少ないですが、実際にはステップが遅くなるため (二分探索は通常、予測が不十分な分岐で実装されます)、より良い方法ではない可能性があります。

ループ定数ではなく、実際に定数である場合は、さらにいくつかのトリックがあります。

  • a0または-1の場合、それは自明です
  • ビットが 1 つしか設定されていない場合aは、次のようにテストできますb != 0 && (b & (b - 1)) == 0
  • 2ビットが設定されている場合a、次のようなテストを実行できますror(b, tzcnt(b)) == ror(a, tzcnt(a))

  • 設定されたビットの連続したグループが 1 つしかない場合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が両方とも変数である場合、これは当てはまりません。

于 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 に答える