Подсчет, обратный битовый паттерн

Question

Я пытаюсь найти алгоритм для подсчета от 0 до 2 ⁿ -1, но их битовая комбинация поменялась местами. Я забочусь только о LSB слова. Как вы уже догадались, я потерпел неудачу.

Для n = 3:

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

Вы поняли идею.

Отлично, ответы в псевдокоде. Фрагменты кода на любом языке приветствуются, предпочтительны ответы без битовых операций.

Пожалуйста, не размещайте фрагмент без краткого объяснения или указателя на источник.

Edit: я забыл добавить, у меня уже есть наивная реализация, которая просто инвертирует переменную count. В некотором смысле этот метод на самом деле не считается.

Answer 1

Возможно увеличить значение от 0 до N («обычный» путь) и выполнить ReverseBitOrder () для каждой итерации. Здесь вы можете найти несколько реализаций (мне нравится LUT одна). Должно быть очень быстро.

Answer 2

void reverse(int nMaxVal, int nBits)
{
   int thisVal, bit, out;

   // Calculate for each value from 0 to nMaxVal.
   for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
   {
      out = 0;

      // Shift each bit from thisVal into out, in reverse order.
      for (bit=0; bit<nBits; ++bit)
         out = (out<<1) + ((thisVal>>bit) & 1)

   }
   printf("%d -> %d\n", thisVal, out);
}