循環シフト

組合せ 数学において、循環シフトとは、組内の要素を並べ替える操作であり、最後の要素を最初の位置に移動し、他のすべての要素を次の位置に移動するか、逆の操作を実行します。循環シフトは、巡回置換の特殊な種類であり、巡回置換は、置換の特殊な種類です。正式には、循環シフトは、組内のn個の要素の置換σであり、次のいずれかになります 。

${\displaystyle \sigma (i)\equiv (i+1)}$ n を法として、すべてのエントリi = 1, ..., nについて

または

${\displaystyle \sigma (i)\equiv (i-1)}$ nを法として、すべてのエントリi = 1, ..., n。

特定のタプルに循環シフトを繰り返し適用した結果は、タプルの 循環シフトとも呼ばれます。

例えば、4つの組（a、b、c、d）に循環シフトを繰り返し適用すると、次のようになります。

• ( d、a、b、c )、
• ( c、d、a、b )、
• ( b、c、d、a )、
• ( a、b、c、d ) (元の4つの組)、

そして、シーケンスが繰り返されます。したがって、この 4 組には 4 つの異なる循環シフトがあります。ただし、すべてのn組にn つの異なる循環シフトがあるわけではありません。たとえば、4 組 ( a、b、a、b ) には 2 つの異なる循環シフトしかありません。 n組の異なる循環シフトの数はです。ここで、kはnの約数であり、すべてのサブパターンでの繰り返しの最大数を示します。 ${\displaystyle {\frac {n}{k}}}$

コンピュータ プログラミングにおいて、ビット回転(循環シフトとも呼ばれる) は、オペランドのすべてのビットをシフトするビット操作です。算術シフトとは異なり、循環シフトでは数値の符号ビットが保持されず、浮動小数点数の指数と仮数部が区別されません。論理シフトとは異なり、空いているビット位置はゼロで埋められるのではなく、シーケンスからシフトされたビットで埋められます。

循環シフトは、暗号技術においてビットシーケンスを並べ替えるためによく使用されます。残念ながら、 C を含む多くのプログラミング言語には、循環シフト用の演算子や標準関数がありません。ただし、事実上すべてのプロセッサには循環シフト用のビット演算命令があります(たとえば、Intel x86には ROL と ROR があります)。ただし、一部のコンパイラは、組み込み関数を使用してプロセッサ命令へのアクセスを提供します。さらに、標準ANSI Cコードの一部の構成要素は、そのような命令を持つ CPU 上の "回転" アセンブリ言語命令にコンパイラによって最適化される場合があります。ほとんどの C コンパイラは次のイディオムを認識し、単一の 32 ビット回転命令にコンパイルします。^{[1] [2]}

/* * C のシフト演算は
、負でなく、sizeof(value) CHAR_BIT より小さいシフト値に対してのみ定義されます。 
* ビットごとの AND (&) で使用されるマスクは、シフト数が 0 または unsigned int の幅以上の場合に未定義の動作を防止します。*/




#include <stdint.h>   // uint32_t の場合、int のサイズに関係なく、32 ビット幅の回転を取得します。#include <limits.h>   // CHAR_BIT の場合 
 

uint32_t rotl32 ( uint32_t値、unsigned intカウント) { const unsigned intマスク= CHAR_BIT * sizeof (値) - 1 ; count &=マスク; return (値<<カウント) | (値>> ( -カウント&マスク)); }       
             
      
             


uint32_t rotr32 ( uint32_t値、unsigned intカウント) { const unsigned intマスク= CHAR_BIT * sizeof (値) - 1 ; count &=マスク; return (値>>カウント) | (値<< ( -カウント&マスク)); }       
             
      
             

この安全でコンパイラフレンドリーな実装はJohn Regehrによって開発され、^[3] Peter Cordesによってさらに改良されました。^{[4] [5]}

countが 1 ～ 31 ビットの範囲に制限されている 場合、より単純なバージョンがよく見られます。

uint32_t rotl32 ( uint32_t値、unsigned intカウント) {戻り値(値<<カウント) | (値>> ( 32 -カウント) ) ); }       
             

countこのバージョンは、 が 0 または 32 の場合に 32 ビット シフトを要求するため危険です。これは、C 言語標準では未定義の動作value >> 32です。ただし、ほとんどのマイクロプロセッサは32 ビット シフト (0 を生成) または 0 ビット シフト (元の を生成value) として実装し、このアプリケーションではどちらでも正しい結果が生成されるため、いずれにせよ機能する傾向があります。

ビットシーケンス 0001 0111 が 1 ビット位置の循環シフトを受けた場合... (下の画像を参照)

ビットシーケンス 1001 0110 に次の操作が実行された場合:

巡回符号は、符号語の巡回シフトによって常に別の符号語が生成されるという特性を持つブロック符号の一種である。このことから、次の一般的な定義が導かれる。アルファベットΣ上の文字列 sについて、sの巡回シフトの集合をshift ( s ) で表し、文字列の集合Lについて、L内のすべての文字列の巡回シフトの集合をshift ( L ) で表す。L が巡回符号である場合、shift ( L ) ⊆ Lとなる。これは、 L が巡回言語であるための必要条件である。演算shift ( L ) は、形式言語理論で研究されてきた。たとえば、L が文脈自由言語である場合、shift ( L ) もやはり文脈自由である。^{[6] [7]また、} L が長さnの正規表現で記述される場合、 shift ( L ) を記述する長さO ( n ³ )の正規表現が存在する。^[8]

• バレルシフター
• 巡回
• リンドンの言葉
• ネックレス—タプルのようなオブジェクトですが、循環シフトは同等であると見なされます。