Rearranging Bits and Bytes

Prev: Searching Words

Next: Multiplication

Sections

• 7-1 Reversing Bits and Bytes
• 7-2 Shuffling Bits
• 7-3 Transposing a Bit Matrix
• 7-4 Compress, or Generalized Extract
• 7-5 Expand, or Generalized Insert
• 7-6 Hardware Algorithms for Compress and Expand
• 7-7 General Permutations, Sheep and Goats Operation
• 7-8 Rearrangements and Index Transformations
• 7-9 An LRU Algorithm

Problems

1. Explain the workings of the second Mobius formula, Equation (1), page 139.

2. The perfect outer shuffle operation and its inverse employ the following masks. What is a formula for the general case, $m_k$? A formula might be useful in situations in which an upper bound on the length of the integers being shuffled is not known in advance, such as in bignum applications.

3. Code a function similar to the compress function of Figure 7-9 that does the expand operation.

4. For an $n$-way set-associative cache, what is the theoretical minimum number of bits required to implement the LRU policy? Compare that to the number of bits required for the reference matrix method, for a few small values of $n$.