3

整数クラスに符号なし左回転を実装したいと考えています。ただし、これはテンプレート クラスであるため、128 ビットから任意のサイズにすることができます。そのため、同じサイズの一時を必要とするアルゴリズムを使用することはできません。型が大きくなると、スタック オーバーフローが発生するためです (特に、そのような関数が呼び出しチェーンにある場合)。

したがって、このような問題を解決するために、質問を最小限に抑えました。4ビットのみを使用して32ビットの数値を回転させるには、どのような手順を実行する必要がありますか. 考えてみれば、32 ビットの数値にはそれぞれ 4 ビットのグループが 8 つ含まれているため、ローテーションするビット数が 4 の場合、グループ0 and 4、1 and 5、2 and 6、の間でスワップが発生3 and 7し、その後ローテーションが行われます。

ローテーションするビットが 4 未満で 0 より大きい場合は、単純に最後のNビットを保存して shift-Or ループを開始します。たとえば、0x9CE2左に 3 ビットローテーションする数値があるとします。

リトル エンディアン バイナリの数値は で1001 1100 1110 0010、各ニブルは右から左に 0 から 3 のインデックスが付けられ、この数値Nと 1 つのグループのビット数を呼びます。B

[1] x <- N[3] >> 3
    x <- 1001 >> 3
    x <- 0100

    y <- N[0] >> (B - 3)
    y <- N[0] >> (4 - 3)
    y <- 0010 >> 1
    y <- 0001

    N[0] <- (N[0] << 3) | x
    N[0] <- (0010 << 3) | 0100
    N[0] <- 0000 | 0100
    N[0] <- 0100


[2] x <- y
    x <- 0001

    y <- N[1] >> (B - 3)
    y <- N[1] >> (4 - 3)
    y <- 1110 >> 1
    y <- 0111

    N[1] <- (N[1] << 3) | x
    N[1] <- (1110 << 3) | 0001
    N[1] <- 0000 | 0001
    N[1] <- 0001


[3] x <- y
    x <- 0111

    y <- N[2] >> (B - 3)
    y <- N[2] >> (4 - 3)
    y <- 1100 >> 1
    y <- 0110

    N[2] <- (N[2] << 3) | x
    N[2] <- (1100 << 3) | 0111
    N[2] <- 0000 | 0111
    N[2] <- 0111


[4] x <- y
    x <- 0110

    y <- N[3] >> (B - 3)
    y <- N[3] >> (4 - 3)
    y <- 1001 >> 1
    y <- 0100

    N[3] <- (N[3] << 3) | x
    N[3] <- (1001 << 3) | 0110
    N[3] <- 1000 | 0110
    N[3] <- 1110

結果は1110 0111 0001 0100、0xE71416 進数で です。これが正しい答えです。そして、任意の精度で任意の数値に適用しようとする場合、必要なのは、その bignum 型を形成する配列の任意の要素の型である 1 つの変数だけです。

実際の問題は、ローテーションするビット数が 1 つのグループよりも大きいか、型の半分のサイズよりも大きい場合 (つまり、この例では 4 ビットまたは 8 ビットよりも大きい場合) です。

通常、最後の要素から最初の要素にビットをシフトします。ただし、最後の要素を最初の要素にシフトした後、回転するビット数が要素 (つまり> 4 bits) よりも大きいため、結果を新しい場所に再配置する必要があります。シフトが開始される開始インデックスは最後のインデックス (この例では 3) であり、宛先インデックスには次の式を使用dest_index = int(bits_count/half_bits) + 1しhalf_bitsます。最初のシフトの結果は宛先インデックス 2 に再配置する必要があります。これが私の問題です。この状況のアルゴリズムを作成する方法が思いつかないからです。half_bits = 8bits_count = 7dest_index = int(7/8) + 1 = 1 + 1 = 2

ありがとう。

4

2 に答える 2

2

ビットローテーションのためにアセンブリ言語関数を呼び出すことをお勧めします。

多くのアセンブリ言語には、キャリーを介したビットのローテーションおよびキャリー スルー ビットのローテーションのためのより優れた機能があります。

多くの場合、アセンブリ言語は C または C++ 関数よりも複雑ではありません。

欠点は、{異なる} プラットフォームごとに各アセンブリ関数のインスタンスが 1 つ必要になることです。

于 2012-06-11T02:05:32.433 に答える
2

これは、これを達成するための 1 つの方法のヒントにすぎません。2 つのパスを作成することを考えることができます。

  • 最初のパス、4 ビット境界のみでローテーション
  • 2 番目のパス、1 ビット境界で回転

したがって、最上位の疑似コードは次のようになります。

rotate (unsigned bits) {
  bits %= 32; /* only have 32 bits */
  if (bits == 0) return;
  rotate_nibs(bits/4);
  rotate_bits(bits%4);
}

したがって、13 ビット回転するには、最初に 3 ニブル回転し、次に 1 ビット回転して、合計 13 ビットの回転を取得します。

ニブルの配列を循環バッファーとして扱うと、ニブルのローテーションを完全に回避できます。次に、ニブルのローテーションは、0インデックスの配列内の開始位置を変更するだけの問題です。

回転を行う必要がある場合は、注意が必要です。8 アイテムの配列をローテーションしていて、ストレージ オーバーヘッドの 1 アイテムだけを使用してローテーションを実行したい場合、3 アイテムずつローテーションするには、次のようにアプローチできます。

   orig: A B C D E F G H
 step 1: A B C A E F G H  rem: D
      2: A B C A E F D H  rem: G
      3: A G C A E F D H  rem: B
      4: A G C A B F D H  rem: E
      5: A G C A B F D E  rem: H
      6: A G H A B F D E  rem: C
      7: A G H A B C D E  rem: F
      8: F G H A B C D E  done

ただし、2、4、または 6 個のアイテム ローテーションで同じ手法を試した場合、サイクルは配列全体には実行されません。そのため、回転数と配列サイズに共通の約数があるかどうかを認識し、アルゴリズムでそれを考慮に入れる必要があります。6段階のローテーションで進むと、さらにいくつかの手がかりが落ちてきます。

   orig: A B C D E F G H
                     A
                 G
             E
         C                 cycled back to A's position
                       B
                   H
               F
           D               done

GCD(6,8) が 2 であることに注意してください。これは、パスごとに 4 回の反復が予想されることを意味します。次に、N 項目配列のローテーション アルゴリズムは次のようになります。

rotate (n) {
  G = GCD(n, N)
  for (i = 0; i < G; ++i) {
    p = arr[i];
    for (j = 1; j < N/G; ++j) {
      swap(p, arr[(i + j*n) % N]);
    }
    arr[i] = p;
  }
}

反復ごとのスワップを回避するために実行できる最適化がありますが、これは演習として残します。

于 2012-06-10T23:55:03.373 に答える