17-1 Bit-reversed binary counter

Chapter 30 examines an important algorithm called the fast Fourier transform, or $\text{FFT}$. The first step of the $\text{FFT}$ algorithm performs a bit-reversal permutation on an input array $A[0..n - 1]$ whose length is $n = 2^k$ 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 $\langle a_{k - 1}, a_{k - 2}, \ldots, a_0 \rangle$, where $a = \sum_{i = 0}^{k - 1} a_i 2^i$. We define

$$\text{rev}_k(\langle a_{k - 1}, a_{k - 2}, \ldots, a_0 \rangle) = \langle a_0, a_1, \ldots, a_{k - 1} \rangle;$$

thus,

$$\text{rev}_k(a) = \sum_{i = 0}^{k - 1} a_{k - i - 1} 2^i.$$

For example, if $n = 16$ (or, equivalently, $k = 4$), then $\text{rev}_k(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 $\text{rev}_k$ that runs in $\Theta(k)$ time, write an algorithm to perform the bit-reversal permutation on an array of length $n = 2^k$ 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 $\text{BIT-REVERSED-INCREMENT}$ that, when given a bit-reversed-counter value $a$, produces $\text{rev}_k(\text{rev}_k(a) + 1)$. If $k = 4$, for example, and the bit-reversed counter starts at $0$, then successive calls to $\text{BIT-REVERSED-INCREMENT}$ produce the sequence

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

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-$\text{AND}$, bitwise-$\text{OR}$, etc. Describe an implementation of the $\text{BIT-REVERSED-INCREMENT}$ procedure that allows the bit-reversal 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?

a. Initialize a second array of length $n$ to all trues, then, going through the indices of the original array in any order, if the corresponding entry in the second array is true, then swap the element at the current index with the element at the bit-reversed position, and set the entry in the second array corresponding to the bit-reversed index equal to false. Since we are running $rev_k < n$ times, the total runtime is $O(nk)$.

b. Doing a bit reversed increment is the same thing as adding a one to the leftmost position where all carries are going to the left instead of the right.

BIT-REVERSED-INCREMENT(a)
    let m be a 1 followed by k - 1 0s
    while m bitwise-AND is not zero
        a = a bitwise-XOR m
        shift m right by 1
    m bitwise-OR a

By a similar analysis to the binary counter (just look at the problem in a mirror), this $\text{BIT-REVERSED-INCREMENT}$ will take constant ammortized time. So, to perform the bit-reversed permutation, have a normal binary counter and a bit reversed counter, then, swap the values of the two counters and increment. Do not swap however if those pairs of elements have already been swapped, which can be kept track of in a auxiliary array.

c. The $\text{BIT-REVERSED-INCREMENT}$ procedure given in the previous part only uses single shifts to the right, not arbitrary shifts.