c - 使用镜像算法进行快速位反转

Question

我在 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;

Answer 1

要理解为什么会这样，首先想一想正常的增量是如何工作的:给定一个任意位模式，增量找到一个连续的运行(可能是空的)直到为零，清除所有的 1，然后设置首先从零到一，像这样:

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 中找到与 Mask 中单独的 1 的位置相匹配的位置零 - 第一个“洞”。循环主体清除目标中的所有 1，从最高阶的开始。循环一停止，Target |= Mask 就会将 1 插入到循环找到的“洞”中。