Bit-reversal permutation とは

応用数学では、ビット反転置換は、n個のアイテムのシーケンスの置換であり、n = 2kは2の累乗である。これは、シーケンスの要素を0からn-1までの数字で索引付けし、これらの数字のそれぞれのバイナリ表現を反転することによって定義されます(これらの2進数のそれぞれが正確に長さkを持つようにパディングされます)。各項目は、この逆の値によって与えられる新しい位置にマップされます。ビット逆転順列は剰余であるため、同じ順列を2回繰り返すことで、その項目の元の順序に戻ります。