1

我包含了来自 Sergey Chernenko 的 FFT 文章中的 C 函数。此函数通过执行奇偶分解来重新排列数据。但是不是使用位反转，而是通过以镜像方式添加 1 来实现，这比我测试过的其他反转代码要快得多。

  /*
      http://www.librow.com/articles/article-10 (Sergey Chernenko)
   */
  void rearrange(float* Data, const unsigned int N) {

     //   Swap position
     unsigned int Target = 0;
     //   Process all positions of input signal
     for (unsigned int Position = 0; Position < N; ++Position)
     {
        //   Only for not yet swapped entries
        if (Target > Position)
        {
           //   Swap entries
           const float Temp = Data[Target];
           Data[Target] = Data[Position];
           Data[Position] = Temp;
        }
        //   Bit mask
        unsigned int Mask = N;
        //   While bit is set
        while (Target & (Mask >>= 1))
           //   Drop bit
           Target &= ~Mask;
        //   The current bit is 0 - set it
        Target |= Mask;
     }
  }

我感兴趣的部分是镜像递增代码。我了解 C 中的按位操作，我可以在脑海中仔细阅读这个片段并验证它是否有效。我还不明白为什么它会起作用。我该如何想出这个解决方案？

        //   Bit mask
        unsigned int Mask = N;
        //   While bit is set
        while (Target & (Mask >>= 1))
           //   Drop bit
           Target &= ~Mask;
        //   The current bit is 0 - set it
        Target |= Mask;
4

2 回答 2

2

要理解为什么会这样，首先考虑一个正常的增量是如何工作的：给定一个任意的位模式，一个增量找到一个连续的运行（可能是空的）直到一个零，清除所有的一，并将第一个零设置为一，像这样：

0000 0001 -  0 ->  1 | No ones at the back (an empty run): insert 1 right away.
0111 1000 -  7 ->  8 | Replace a run of three ones with zeros, then insert 1
1011 1100 - 11 -> 12 | Replace a run of two ones with zeros, then insert 1

现在考虑您的算法：常规增量检测从数字后面开始的运行；您的循环检测从数字前面开始的运行。由于您说算法“以镜像方式添加一个”，N因此必须是Target. while循环试图找到一个位置，Target其中孤独的位置与1零Mask匹配 - 第一个“洞”。循环体清除目标中所有的，从最高阶的开始。一旦循环停止，Target |= Mask插入1到循环找到的“洞”中。

于 2013-06-07T09:12:31.053 回答
1

它只是在逐个位置模拟 1 的加法。除了位置颠倒。

要加 1，您不断修改位位置（从最低有效位开始），直到不再有进位。

于 2013-06-07T09:09:48.657 回答