Bit-reversed binary counter

Chapter 30 examines an important algorithm called the Fast Fourier Transform, or FFT. The first step of the FFT algorithm performs a bit-reversal permutation on an input array A[0 ? n - 1] whose length is n= 2k for some nonnegative integer k. This permutation swaps elements whose indices have binary representations that are the reverse of each other. We can express each index a as a k-bit sequence ?ak-1, ak-2, ..., a0?, where . We define

For example, if n = 16 (or, equivalently, k = 4), then revk(3) = 12, since the 4-bit representation of 3 is 0011, which when reversed gives 1100, the 4-bit representation of 12.

a. Given a function revk that runs in Φ(k) time, write an algorithm to perform the bitreversal permutation on an array of length n = 2k in O(nk) time.

We can use an algorithm based on an amortized analysis to improve the running time of the bit-reversal permutation. We maintain a "bit-reversed counter" and a procedure BITREVERSED- INCREMENT that, when given a bit-reversed-counter value a, produces revk(revk(a) + 1). If k = 4, for example, and the bit-reversed counter starts at 0, then successive calls to BIT-REVERSED-INCREMENT produce the sequence

0000, 1000, 0100, 1100, 0010, 1010, ... = 0, 8, 4, 12, 2, 10, ... .

b. Assume that the words in your computer store k-bit values and that in unit time, your computer can manipulate the binary values with operations such as shifting left or right by arbitrary amounts, bitwise-AND, bitwise-OR, etc. Describe an implementation of the BIT-REVERSED-INCREMENT procedure that allows the bitreversal permutation on an n-element array to be performed in a total of O(n) time.

c. Suppose that you can shift a word left or right by only one bit in unit time. Is it still possible to implement an O(n)-time bit-reversal permutation?