使用镜像算法的快速比特反转

Question

我包含了谢尔盖·切尔年科在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(可能是空的)，直到0为止，清除所有的1，并将第一个0设置为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

现在考虑您的算法:规则增量检测从数字后面开始的运行；您的循环检测从数字前面开始的运行。既然你说算法“以镜像的方式加1”，那么N必须是Target中可能存在的2的最高幂的两倍。while循环试图在Target中找到一个位置，其中Mask中唯一的1的位置与零匹配-第一个“洞”。循环体清除目标中的所有1，从最高顺序的1开始。循环一停止，Target |= Mask就会将1插入到循环找到的“洞”中。

Answer 2

它只是模拟1的加法，一个位置接着一个位置。除非位置颠倒了。

要添加1，您需要不断修改位位置(从最低有效位开始)，直到不再有进位。