Go back to Richel Bilderbeek's homepage.

Go back to Richel Bilderbeek's C++ page.

 

 

 

 

 

(C++) GetGrayCodes

 

GetGrayCodes is a bit operation code snippet to generate the Gray code for 1 to and including 16 bits. It does so by flipping a single bit and checking if this number has been used already.

 

Related functions to GetGrayCodes are GrayToInt and IntToGray.

 

#include <iostream>
#include <bitset>
#include <vector>
#include <cassert>
#include <cmath>
#include <boost/static_assert.hpp>

//From http://www.richelbilderbeek.nl/CppGetGrayCodes.htm
template <int N>
std::vector<std::bitset<N> > GetGrayCodes()
{
  BOOST_STATIC_ASSERT( N > 0 && N <= 16);

  const int nCodes = std::pow(static_cast<double>(2),N);

  //Check if std::pow does its job correctly
  assert( N != 4 || ( N == 4 && nCodes == 16) );
  assert( N != 8 || ( N == 8 && nCodes == 256) );
  assert( N != 16 || ( N == 16 && nCodes == 65536) );

  std::vector<std::bitset<N> > v;
  v.reserve(nCodes);
  std::bitset<N> b(1); //1 so that the first itertion of loop i succeeds

  for (int i=0; i!=nCodes; ++i)
  {
    //Search for a bitset not in the std::map
    //that only differs in one bit
    //starting from the least significant bit
    for (int bit=0; bit!=N; ++bit)
    {
      std::bitset<N> bTest(b); //Copy b to bTest
      bTest.set(bit, !bTest.test(bit) ); //Flip one bit
      if (std::find(v.begin(), v.end(), bTest) == v.end() )
      {
        //Unique bitset found!
        //Add to std::vector
        b = bTest;
        v.push_back(b);
        break;
      }
      //Bitset already in std::map
      //Try next bit...
    }
  }
  assert(nCodes == static_cast<int>(v.size()));
  return v;
}

int main()
{
  const int nBits = 8;
  typedef std::vector<std::bitset<nBits> > BitVector;
  typedef BitVector::const_iterator Iterator;

  const BitVector v(GetGrayCodes<nBits>());

  //Show the correct vector
  for (Iterator i = v.begin(); i!=v.end(); ++i)
  {
    std::cout << std::distance(v.begin(), i) << " : " << *i << std::endl;
  }

  std::cin.get();
}

 

 

 

 

 

External links

 

  1. Wikipedia’s page about Gray Codes

 

 

 

 

 

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

 

Valid XHTML 1.0 Strict