### 7-6 Rearrangements and Index Transformations

Many simple rearrangements of the bits in a computer word correspond to even simpler transformations of the coordinates, or indexes, of the bits [GLS1]. These correspondences apply to rearrangements of the elements of any one-dimensional array, provided the number of array elements is an integral power of 2. For programming purposes, they are useful primarily when the array elements are a computer word or larger in size.

As an example, the outer perfect shuffle of the elements of an array A of size eight, with the result in array B, consists of the following moves:

Each B-index is the corresponding A-index rotated left one position, using a 3-bit rotator. The outer perfect unshuffle is of course accomplished by rotating right each index. Some similar correspondences are shown in Table 7-1. Here n is the number of array elements, "lsb" means least significant bit, and the rotations of indexes are done with a log2n-bit rotator.

##### Table 7-1. Rearrangements and Index Transformations

Index Transformation

Rearrangement

Array Index, or Big-endian Bit Numbering

Little-endian Bit Numbering

Reversal

Complement

Complement

Bit flip, or generalized reversal (page 102)

Exclusive or with a constant

Exclusive or with a constant

Rotate left k positions

Subtract k (mod n)

Rotate right k positions

Subtract k (mod n)

Outer perfect shuffle

Rotate left one position

Rotate right one position

Outer perfect unshuffle

Rotate right one position

Rotate left one position

Inner perfect shuffle

Rotate left one, then complement lsb

Complement lsb, then rotate right one

Inner perfect unshuffle

Complement lsb, then rotate right

Rotate left one, then complement lsb

Transpose of an 8x8-bit matrix held in a 64-bit word

Rotate (left or right) three positions

Rotate (left or right) three positions

FFT unscramble

Reverse bits

Reverse bits