Hacker's Delight

7-2. Shuffling Bits

Another important permutation of the bits of a word is the “perfect shuffle” operation, which has applications in cryptography. There are two varieties, called the “outer” and “inner” perfect shuffles. They both interleave the bits in the two halves of a word in a manner similar to a perfect shuffle of a deck of 32 cards, but they differ in which card is allowed to fall first. In the outer perfect shuffle, the outer (end) bits remain in the outer positions, and in the inner perfect shuffle, bit 15 moves to the left end of the word (position 31). If the 32-bit word is (where each letter denotes a single bit)

abcd efgh ijkl mnop ABCD EFGH IJKL MNOP, 

then after the outer perfect shuffle it is

 aAbB cCdD eEfF gGhH iIjJ kKlL ...