（位逆序的二进制计数器）FFT算法的第一步是对一个输入数组A[0..n-1]执行一次称为位逆序置换（bit-reversal permutation）的操作，数组的长度为n=2k。k是一个非负整数，这个置换操作将下标的二进制表示互为逆序的数组元素进行交换。
我们将每个下标a表示为一个k位二进制序列<ak-1,ak-2,...,a0>，其中a=
。我们定义
因此，
假如，若n=16（或等价的k=4），则revk(3)=2，因为3的4位二进制表示为0011，其逆序为1100，是12的4位二进制表示。
a.设计一个运行时间为)
的函数revk，编写算法在O(nk)时间内最长度为n=2k的数组执行位逆序置换。
我们可以使用一个基于摊还分析的算法来改进位逆序置换操作的运行时间。我们可以维护一个位逆序计数器，并设计一个过程BIT-REVERSED-INCREMENT，当给定一个位逆序计数器值a，该过程能得到revk(revk(a)+1)。假如，若k=4，位逆序计数器从0开始，则连续调用BIT-REVERSED-INCREMENT会得到序列：
0000,1000,0100,1100,0010,1010,....=0,8,4,12,2,10，...
b.假定你的计算机的每个机器字保存k位二进制，而每个机器中的值进行一次任意偏移量的左/右移位，位与，位或等操作只需单位时间，设计一个BIT-REVERSED-INCREMENT过程，能使一个n个元素的数组上的位逆序置换操作在O(n)时间内完成。
c.假定在单位时间内你只能完成左右移一位的操作，还可以实现O(n)时间的位逆序置换操作吗？
