Gray Code Generator

graycode.cc

#include <bitset>
#include <iostream>

template <size_t N>
using GrayCode = std::bitset<N>;

// Construct the binary-reflected Gray code iteratively.
template <size_t N>
class GrayCodeGenerator {
 public:
  bool Next(GrayCode<N> &out) {
    if (n == (1 << N)) {
      return false;
    }

    if (n == 0) {
      out = code.reset();
    } else {
      // find the bit position of the least significant 1 of n
      size_t pos = 0;
      for (; pos < N; pos++) {
        if ((n & (1 << pos)) > 0) {
          break;
        }
      }
      out = code.flip(pos);
    }

    n++;
    return true;
  }

 private:
  GrayCode<N> code;
  int n = 0;
};

template <size_t N>
class GrayCodeGeneratorFast {
 public:
  bool Next(GrayCode<N> &out) {
    if (n == (1 << N)) {
      return false;
    }

    out = GrayCode<N>((n >> 1) ^ n);
    n++;
    return true;
  }

 private:
  int n = 0;
};

int main(int argc, char *argv[]) {
  GrayCode<4> code;

  // obtain next gray code
  for (GrayCodeGenerator<4> generator1; generator1.Next(code);) {
    std::cout << code.to_string() << std::endl;
  }

  std::cout << std::endl;

  for (GrayCodeGeneratorFast<4> generator2; generator2.Next(code);) {
    std::cout << code.to_string() << std::endl;
  }

  return 0;
}