c - 数组上的就地位反转随机播放

Question

对于 FFT 函数，我需要以位反转方式排列或随机排列数组中的元素。这是 FFT 的一项常见任务，因为大多数二次方大小的 FFT 函数都以位反转的方式期望或返回它们的数据。

例如假设该数组有 256 个元素，我想用它的位反转模式交换每个元素。这里有两个例子(二进制):

Element 00000001b should be swapped with element 10000000b
Element 00010111b should be swapped with element 11101000b

等等。

知道如何快速且更重要地做到这一点吗:就地？

我已经有一个函数可以进行这种交换。写一个并不难。由于这是 DSP 中的常见操作，我感觉有比我非常幼稚的循环更聪明的方法来完成它。

有问题的语言是 C，但任何语言都可以。

Answer 1

要通过一次传递就地交换，以递增索引遍历所有元素一次。仅当索引小于反向索引时才执行交换——这将跳过双重交换问题和回文情况(元素 00000000b、10000001b、10100101b)，它们反向为相同的值并且不需要交换。

// Let data[256] be your element array 
for (i=0; i<256; i++)
    j = bit_reverse(i);
    if (i < j)
    {
        swap(data[i],data[j]);
    }

bit_reverse() 可以使用 Nathaneil 的位运算技巧。 bit_reverse() 将被调用 256 次，而 swap() 将被调用不到 128 次。