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++.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| #include <sstream> | |
| using namespace std; | |
| vector<string> grayCode(int n) | |
| { | |
| vector<string> arr; | |
| // start with one-bit pattern | |
| arr.push_back("0"); | |
| arr.push_back("1"); | |
| //implement reverse copy and append 0/1 | |
| int i, j; | |
| for (i = 2; i < (1<<n); i = i<<1) | |
| { | |
| //duplicate the arr contents in reverse order | |
| for (j = i-1 ; j >= 0 ; j--) | |
| arr.push_back(arr[j]); | |
| // append 0 to the first half | |
| for (j = 0 ; j < i ; j++) | |
| arr[j] = "0" + arr[j]; | |
| // append 1 to the second half | |
| for (j = i ; j < 2*i ; j++) | |
| arr[j] = "1" + arr[j]; | |
| } | |
| return arr; | |
| } | |
| int main() | |
| { | |
| vector<string> codes = grayCode(3); | |
| for( int i = 0; i < codes.size(); i++ ) | |
| { | |
| cout << codes[i] << " "; | |
| } | |
| return 0; | |
| } |
by