FFT - инвертирование бит

[MooNDeaR]

Для расчета БПФ данные для удобства приводят к нижней итерации, т.е. к тому состоянию, когда массив с данными уже разбит на блоки и перемешан (см. рисунок строчка 3).



Когда реализовывал сам, я их перемешивал в 2 цикла: один следит за размером текущего блока, другой меняет четные/нечетные позиции местами. Но порывшись в интернете, наткнулся на вот такой код для перемешивания:

/*
 * Учитывая ряд х, возвращает число которое имеет те же биты как Х но в обратном порядке
 */
inline unsigned int backwards(unsigned int x, int length)
{
   unsigned int result = 0;
   unsigned int bit = 1u;
   unsigned int reverse = 1u<<(length-1);
   for(int i = 0; i < length && x != 0; i++) {
      if(x & bit) {
         result |= reverse;
         x &= ~bit;
      }
      bit <<= 1;
      reverse >>= 1;
   }
   return result;
}

static void reposition(comp *array, int size)
{
   // Определяем длину в битах
   int length = 0;
   while(1u << length < (unsigned int)size)
      length++;

   // Обмен элементов в позициях k и reverse(k)
   for(int i = 0; i < size; i++) {
      int j = backwards(i, length);
      if(i <= j)
         swap(array[i], array[j]);
   }
}

Что характерно, он работает и перемешивает массив в один проход, а результат тот же. Я уже головой об стену бьюсь, но не могу понять почему так происходит. Т.е. я хочу разобраться, по какой логике появилась такая зависимость от "реверсии" бит.

Может кто знает или может кинуть инфы в чем же здесь суть, т.к. гугл молчит.

[MooNDeaR]

Ну и ладно...