76
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 onedimensional
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 Bindex
is the corresponding Aindex rotated left one
position, using a 3bit rotator. The outer perfect unshuffle
is of course accomplished by rotating right
each index. Some similar correspondences are shown in Table 71. Here n is the number of array elements, "lsb"
means least significant bit, and the rotations of indexes are done with a log_{2}nbit rotator.
Table 71.
Rearrangements and Index Transformations


Index Transformation

Rearrangement

Array Index, or Bigendian Bit
Numbering

Littleendian 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 8x8bit matrix held in a 64bit word

Rotate (left or right) three positions

Rotate (left or right) three positions

FFT unscramble

Reverse bits

Reverse bits
