algorithm - サーキュラーシフトの応用

Question

循環シフトの適用例をいくつか知りたいです。たとえば、符号なし整数を右シフトすると、2 で除算されます。逆に、左シフトは 2 の乗算になります。2 進数の循環シフトの有名な/興味深い特性はありますか。

注: 右/左シフトに関する例は、その特定の演算子の適用を説明するためのものです。循環シフト演算子/関数の同様の例を求めています。

Answer 1

• 16 ビット ワードをビッグ エンディアン表現とリトル エンディアン表現の間で変換します。右または左に 8 循環シフトします。
• 偶数のビット セットでランダム ビットセットを生成します: t = rand(); result = t XOR cshift(t,1).
• インプレース、安定、線形時間: 偶数位置の配列のすべての要素を最初に移動し、奇数位置のすべての要素を最後に移動します。可能なアルゴリズムの 1 つがこの論文で説明されています。可能なすべてのバイナリ ネックレスを生成し、循環シフトによって前の位置から次の位置を計算するサイクル リーダー アルゴリズムの開始点としてそれらを使用します。2 (mod (2^N - 1))このアプリケーションは、ヘンリックの回答で言及されている乗算と密接に関連しています。
• マイクロ最適化。1 バイトから 4 つの 2 ビット ワードをアンパックする必要があるとします。これを行うには、各サブワードを右端の位置にシフトしてから、適切なマスクを使用して AND 演算を適用します。(最初のサブワードをシフトしたり、最後のサブワードをマスクしたりする必要はありません)。これには 6 つの CPU 命令が必要です。バイトを循環的に 4 シフトすると、中間の 2 つのサブワードが最初と最後のサブワードになり、それぞれに 1 つの命令しか必要ありません。したがって、循環シフトを使用すると、必要な命令の数が 5 に減少します。
• 機械命令セットにローテーション命令が含まれている場合、暗号化アプリケーションは大幅に高速化されます。たとえば、Twofish Cipher は循環シフトを広範囲に使用します。