Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit.
For example 2-bit gray code is shown below.
00
01
11
10
Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray code is explained below. An n-bit gray code can be generated from (n-1) bit gray code as follows.
1-bit gray code is obvious; it is 0,1.
2-bit gray code can be generated as follows.
- Expand the sequence by adding it’s elements in reverse order (in this case 1, 0).
- Prepend zeros to the first half and Ones to the second Half
0 0
0 1
—–
1 1
1 0
3-bit gray code can be generated similarly.
0 00
0 01
0 11
0 10
——
1 10
1 11
1 01
1 00
Below is the implementation of this algorithm in C++.