Code Poetry
and Text Adventures

by catid posted (>30 days ago) 4:47pm Tue. Dec 13th 2016 PST
4-bit Gray Codes are binary sequences that flip one bit instead of adding one each time to get to the next sequence element.

#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;

int only_one_bit_set_to_one(uint32_t b)
{
   return b && !(b & (b - 1));
}

bool hamming1(uint32_t a, uint32_t b)
{
   return only_one_bit_set_to_one(a ^ b);
}

void shuffleTable(uint8_t* table, int offset)
{
   if (offset == 16)
   {
      cout << "static const uint8_t GrayCode[16]            = { ";
      for (int i = 0; i < 16; ++i)
      {
           cout << (int)table[i];
           if (i != 15)
               cout << ", ";
      }
      cout << " };" << endl;
#if 1
      cout << "static const uint8_t AccumulatedPopCount[16] = { ";
      uint8_t acc = 0;
      for (int i = 0; i < 16; ++i)
      {
           acc |= table[i];

           cout << __popcnt(acc);

           if (i != 15)
               cout << ", ";
      }
      cout << " };" << endl;
#endif
#if 1
      cout << "static const uint8_t FlipIndices[15]         = { ";
      for (int i = 1; i < 16; ++i)
      {
           uint8_t delta = table[i] ^ table[i - 1];
           if (!only_one_bit_set_to_one(delta))
           {
               cout << "FAILURE" << endl;
           }
           unsigned long index = 0;
           if (1 != _BitScanForward(&index, delta))
           {
               cout << "FAILURE" << endl;
           }

           cout << index;
           if (i != 15)
               cout << ", ";
      }
      cout << " };" << endl;
#endif
      cout << endl;
      return;
   }

   uint8_t y = table[offset - 1];

   for (int i = offset; i < 16; ++i)
   {
      uint8_t x = table[i];

      if (hamming1(x, y))
      {
           table[i] = table[offset];
           table[offset] = x;

           shuffleTable(table, offset + 1);

           table[offset] = table[i];
           table[i] = x;
      }
   }
}

void Generate4BitGrayCode()
{
   uint8_t table[16] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

   shuffleTable(table, 2);
}

int main()
{
   Generate4BitGrayCode();

   return 0;
}

Output: http://pastebin.com/rKUretrH
last edit by catid edited (>30 days ago) 4:58pm Tue. Dec 13th 2016 PST