// Gray code is a binary code where each successive value differ in only one bit, as well as when wrapping around.
// Gray code is common in hardware so that we don't see temporary spurious values during transitions.
// Given a number of bits n, generate a possible gray code for it.
// For example, for n = 2, one gray code would be[00, 01, 11, 10].
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> GreyCode(int n)
{
vector<string> vec;
if (n <= 0)
return vec;
// start with one-bit pattern so we can duplicate it
vec.push_back("0");
vec.push_back("1");
int j;
for (int i = 2; i < (1 << n); i = i << 1)
{
// Reenter all values in vec[] but in reverse
for (j = i - 1; j >= 0; j--)
vec.push_back(vec[j]);
// append 0 to the first half of the entries
for (j = 0; j < i; j++)
vec[j] = "0" + vec[j];
// append 1 to the second half of the entries
for (j = i; j < 2 * i; j++)
vec[j] = "1" + vec[j];
}
return vec;
}
int main()
{
vector<string> vec = GreyCode(4);
for (int i = 0; i < vec.size(); i++)
cout << vec[i] << endl;
return 0;
}
Comments