Gray Code

A Gray code is a list of all 2^n bit strings of length, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one). source 

The problem is, how to generate Gray Code for a given length n. 

When n = 2 , Gray Code : 

00 01 11 10

When n = 3, Gray Code :

000 001 011 010 110 111 101 100

000(0) position Gray code string 000 

001(1) -> 001 

010(2) -> 011 

011(3) -> 010

..... 

Key observation - 

For the K position, the Gray code string is S.  

if i and (i+1)-th bit of K is equal then i-th char of S will be  '0', otherwise, it will be '1'.  

Code : 

           int n; cin >> n;

    for(int i = 0; i < (1 << n); i++) {

        int value =  ( i ^ (i >> 1) ) ;

        string s = "";

        for(int j = 0; j < n; j++) {

            if( value & (1 << j) )s.push_back('1');

            else s.push_back('0');

        }

        reverse( s.begin(), s.end() );

        cout << s << ' ';

    }