(C++) GetGrayCodes
February 24, 2017 · View on GitHub
(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