Circular shift とは

コンビナトリアル数学では、循環シフトとは、タプルのエントリを並べ替える操作です。最後のエントリを最初の位置に移動し、他のすべてのエントリを次の位置にシフトするか、逆の操作を実行します。循環シフトは特別な種類の巡回置換であり、順列は特殊な並べ替えである。正式には、循環シフトは、タプル内のn個のエントリの順列σであり、その結果、
σ ( i ) ( i + 1 ) {\displaystyle \sigma (i)\equiv (i+1)} modulo n、すべてのエントリi = 1、…、n
または
σ ( i ) ( i 1 ) {\displaystyle \sigma (i)\equiv (i-1)} すべてのエントリi = 1、…、nに対してモジュロn。
与えられたタプルに循環シフトを繰り返し適用した結果をタプルの循環シフトともいいます。
たとえば、4タプル(a、b、c、d)に循環シフトを繰り返し適用すると、
 (元の4タプル)、(a、b、c、d)(d、a、b、c)、(c、d、a、b)
シーケンスが繰り返されます。したがって、この4タプルは4つの異なる循環シフトを有する。しかしながら、すべてのnタプルがn個の異なる循環シフトを有するわけではない。例えば、4タプル(a、b、a、b)は2つの異なる循環シフトしか持たない。一般に、nタプルの循環シフトの数は、タプルのエントリに応じてnの任意の除数とすることができる。
コンピュータプログラミングでは、循環シフト(またはビット回転)は、そのオペランドのすべてのビットをシフトするシフト演算子です。算術シフトとは異なり、循環シフトは数値の符号ビットを保持したり、数値の指数をその仮数と区別したりしません(時には仮数とも呼ばれます)。論理シフトとは異なり、空のビット位置はゼロで埋められませんが、シーケンスからシフトされたビットで埋められます。