c - 阵列上的原位反转混洗

对于FFT函数，我需要以位反转的方式对数组中的元素进行置换或混洗。这是FFT的常见任务，因为两种大小的FFT函数的大多数功能都是以位反转的方式期望或返回其数据。

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

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

等等。

任何想法如何快速，更重要地做到这一点:就地吗？

我已经有一个执行此交换的功能。写一个不难。由于这是DSP中的常见操作，因此我觉得比我非常幼稚的循环有更多巧妙的方法来执行此操作。

所讨论的语言是C，但是任何一种语言都可以。

最佳答案

要通过一次传递就地交换，请对递增索引中的所有元素进行一次迭代。仅当索引小于反向索引时才执行交换-这将跳过双重交换问题，并且回文情况(元素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次。

关于c - 阵列上的原位反转混洗，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/932079/