就地位反转洗牌的阵列上 [英] in-place bit-reversed shuffle on an array

问题描述

对于FFT功能，我需要排列替换或位反转的方式在阵列内洗牌的元素。这是一个共同的任务，因为FFT的两种尺寸的FFT功能，最大功率要么期望或位反转的方式回报他们的数据。

For a FFT function I need to permutate or shuffle the elements within an array in a bit-reversed way. That's a common task with FFTs because most power of two sized FFT functions either expect or return their data in a bit-reversed way.

例如。假设数组有256元，我想交换的每个元素与它的位反转格局。这里有两个例子（二进制）：

E.g. assume that the array has 256 elements I'd like to swap each element with it's bit-reversed pattern. Here are two examples (in binary):

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

等。

任何想法如何做到这一点快，更重要的是：在地方？

Any idea how to do this fast and more important: in-place?

我已经有做这个交换的功能。这并不难写一个。由于这是在DSP这样一个共同的操作我有更聪明的方式来做到这一点比我非常naiive循环的感觉。

I already have a function that does this swap. It's not hard to write one. Since this is such a common operation in DSP I have the feeling that there are more clever ways to do it than my very naiive loop.

中的语言问题是C，但任何语言是好的。

Language in question is C, but any language is fine.

推荐答案

要到位的单程交换，通过增加索引的所有元素重复一次。执行交换只有如果索引小于反向索引 - 这将跳过双交换问题，也回文案件逆为相同的值，也没有交换需要（元素00000000B，10000001b，10100101B）

To swap in place with a single pass, iterate once through all elements in increasing index. Perform a swap only if the index is less-than the reversed index -- this will skip the double swap problem and also palindrome cases (elements 00000000b, 10000001b, 10100101b) which inverse to the same value and no swap is required.

// 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次，​​但交换（）将会被调用少于128倍。

The bit_reverse() can be using Nathaneil's bit-operations trick. The bit_reverse() will be called 256 times but the swap() will be called less than 128 times.

这篇关于就地位反转洗牌的阵列上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！