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

これが機能する理由を理解するには、まず通常のインクリメントがどのように機能するかを考えてください。任意のビット パターンが与えられた場合、インクリメントは 0 になるまで連続する 1 の実行 (空の可能性があります) を見つけ、すべての 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に存在する可能性のある2の最高乗の2倍でなければなりませんTarget。ループは、内のローンの位置がゼロに一致する位置、つまり最初の「穴」whileを見つけようとします。ループの本体は、最上位のものから始めて、ターゲット内のすべての 1 をクリアします。ループが停止するとすぐに、ループによって見つかった「穴」に挿入されます。Target1MaskTarget |= Mask1

于 2013-06-07T09:12:31.053 に答える
1

位置ごとに1で加算をエミュレートしているだけです。位置が逆であることを除いて。

1 を追加するには、キャリーがなくなるまでビット位置を (最下位から開始して) 変更し続けます。

于 2013-06-07T09:09:48.657 に答える