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.
| 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 8×8-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 |