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 log₂n-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)	Add k (mod n)
Rotate right k positions	Add k (mod n)	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