Generate n bit gray code
In this article, we will explore how to generate n-bit Gray code. Gray code is a binary numeral system where two successive values differ in only one bit. It finds applications in various areas, including telecommunications, error detection, and analog-to-digital converters.
Problem Statement
The problem at hand is to generate n-bit Gray code. Gray code is a binary numeral system in which two successive values differ in only one bit. The task is to create a program that can generate all possible n-bit Gray codes.
To better understand the problem, let's consider an example with n = 3. In a 3-bit Gray code, we want to generate a sequence of numbers where each number differs from the previous number by only one bit. The expected output for n = 3 is [0, 1, 3, 2, 6, 7, 5, 4]. Here, each number in the sequence has a binary representation, and consecutive numbers have only one bit difference.
Given an integer n, we need to generate all possible n-bit Gray codes. For example, if n = 2, the Gray code sequence would be [0, 1, 3, 2].
Example
Let's consider an example with n = 3 to understand the concept better.
For n = 3, the expected output is:
[0, 1, 3, 2, 6, 7, 5, 4]
Here, the binary representation of the decimal numbers in the output sequence is:
000 001 011 010 110 111 101 100
As you can observe, each number in the sequence differs from the previous number by only one bit.
Pseudocode Algorithm
To generate the n-bit Gray code sequence, we can use a recursive approach. Here is the pseudocode algorithm:
function grayCode(n, code): if n = 0: print code return grayCode(n - 1, code) code = code XOR (1 << (n - 1)) grayCode(n - 1, code) function findGrayCode(n): if n <= 0: return print "(n) Bit gray code" code = 0 grayCode(n, code)
The grayCode
function recursively generates the Gray code sequence by XORing the code with a specific bit position. The findGrayCode
function serves as an entry point and prints the gray code sequence for a given value of n.
Explanation
Now, let's walk through the code and understand how it works.
The grayCode
function takes two parameters: n (the number of bits) and code (the current gray code value). It checks if n is equal to 0. If so, it prints the code and returns. This is the base case for the recursive function.
If n is not 0, the function makes two recursive calls:
- First, it calls
grayCode
with n - 1 and the same code value. - Then, it XORs the code with (1 << (n - 1)) to toggle the bit at position n - 1.
- Finally, it calls
grayCode
again with n - 1 and the updated code value.
This recursive approach generates the gray code sequence by considering the gray code for n - 1 bits and then modifying it by toggling the nth bit.
The findGrayCode
function acts as a wrapper function that calls grayCode
for the specified value of n and prints the gray code sequence.
Code Solution
/*
C Program for
Generate n bit gray code
*/
#include <stdio.h>
// Print gray code
void grayCode(int n, int *code)
{
if (n == 0)
{
// Display calculate code
printf("\n %d", *code);
return;
}
grayCode(n - 1, code);
// Calculate gray code
*code = *code ^ (1 << (n - 1));
grayCode(n - 1, code);
}
// Handles the request to find gray code
void findGraycode(int n)
{
if (n <= 0)
{
return;
}
printf("\n (%d) Bit gray code ", n);
int code = 0;
grayCode(n, & code);
printf("\n");
}
int main()
{
int n = 4;
// Test when n = 4
findGraycode(n);
n = 5;
// Test when n = 5
findGraycode(n);
return 0;
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
/*
Java Program for
Generate n bit gray code
*/
public class GenerateGrayCode
{
public int code;
public GenerateGrayCode()
{
this.code = 0;
}
// Print gray code
public void grayCode(int n)
{
if (n == 0)
{
// Display calculate code
System.out.print("\n " + this.code );
return;
}
grayCode(n - 1);
// Calculate gray code
this.code = this.code ^ (1 << (n - 1));
grayCode(n - 1);
}
// Handles the request to find gray code
public void findGraycode(int n)
{
if (n <= 0)
{
return;
}
System.out.print("\n (" + n + ") Bit gray code ");
this.code = 0;
grayCode(n);
System.out.print("\n");
}
public static void main(String[] args)
{
GenerateGrayCode task = new GenerateGrayCode();
int n = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Generate n bit gray code
*/
class GenerateGrayCode
{
public: int code;
GenerateGrayCode()
{
this->code = 0;
}
// Print gray code
void grayCode(int n)
{
if (n == 0)
{
// Display calculate code
cout << "\n " << this->code;
return;
}
this->grayCode(n - 1);
// Calculate gray code
this->code = this->code ^ (1 << (n - 1));
this->grayCode(n - 1);
}
// Handles the request to find gray code
void findGraycode(int n)
{
if (n <= 0)
{
return;
}
cout << "\n (" << n << ") Bit gray code ";
this->code = 0;
this->grayCode(n);
cout << "\n";
}
};
int main()
{
GenerateGrayCode task = GenerateGrayCode();
int n = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
return 0;
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
// Include namespace system
using System;
/*
C# Program for
Generate n bit gray code
*/
public class GenerateGrayCode
{
public int code;
public GenerateGrayCode()
{
this.code = 0;
}
// Print gray code
public void grayCode(int n)
{
if (n == 0)
{
// Display calculate code
Console.Write("\n " + this.code);
return;
}
grayCode(n - 1);
// Calculate gray code
this.code = this.code ^ (1 << (n - 1));
grayCode(n - 1);
}
// Handles the request to find gray code
public void findGraycode(int n)
{
if (n <= 0)
{
return;
}
Console.Write("\n (" + n + ") Bit gray code ");
this.code = 0;
grayCode(n);
Console.Write("\n");
}
public static void Main(String[] args)
{
GenerateGrayCode task = new GenerateGrayCode();
int n = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
<?php
/*
Php Program for
Generate n bit gray code
*/
class GenerateGrayCode
{
public $code;
function __construct()
{
$this->code = 0;
}
// Print gray code
public function grayCode($n)
{
if ($n == 0)
{
// Display calculate code
echo "\n ". $this->code;
return;
}
$this->grayCode($n - 1);
// Calculate gray code
$this->code = $this->code ^ (1 << ($n - 1));
$this->grayCode($n - 1);
}
// Handles the request to find gray code
public function findGraycode($n)
{
if ($n <= 0)
{
return;
}
echo "\n (". $n .") Bit gray code ";
$this->code = 0;
$this->grayCode($n);
echo "\n";
}
}
function main()
{
$task = new GenerateGrayCode();
$n = 4;
// Test when n = 4
$task->findGraycode($n);
$n = 5;
// Test when n = 5
$task->findGraycode($n);
}
main();
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
/*
Node Js Program for
Generate n bit gray code
*/
class GenerateGrayCode
{
constructor()
{
this.code = 0;
}
// Print gray code
grayCode(n)
{
if (n == 0)
{
// Display calculate code
console.log(" "+this.code);
return;
}
this.grayCode(n - 1);
// Calculate gray code
this.code = this.code ^ (1 << (n - 1));
this.grayCode(n - 1);
}
// Handles the request to find gray code
findGraycode(n)
{
if (n <= 0)
{
return;
}
console.log(" (" + n + ") Bit gray code ");
this.code = 0;
this.grayCode(n);
console.log("\n");
}
}
function main()
{
var task = new GenerateGrayCode();
var n = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
main();
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
# Python 3 Program for
# Generate n bit gray code
class GenerateGrayCode :
def __init__(self) :
self.code = 0
# Print gray code
def grayCode(self, n) :
if (n == 0) :
# Display calculate code
print("\n ", self.code, end = "")
return
self.grayCode(n - 1)
# Calculate gray code
self.code = self.code ^ (1 << (n - 1))
self.grayCode(n - 1)
# Handles the request to find gray code
def findGraycode(self, n) :
if (n <= 0) :
return
print("\n (", n ,") Bit gray code ", end = "")
self.code = 0
self.grayCode(n)
print(end = "\n")
def main() :
task = GenerateGrayCode()
n = 4
# Test when n = 4
task.findGraycode(n)
n = 5
# Test when n = 5
task.findGraycode(n)
if __name__ == "__main__": main()
Output
( 4 ) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
( 5 ) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
# Ruby Program for
# Generate n bit gray code
class GenerateGrayCode
# Define the accessor and reader of class GenerateGrayCode
attr_reader :code
attr_accessor :code
def initialize()
self.code = 0
end
# Print gray code
def grayCode(n)
if (n == 0)
# Display calculate code
print("\n ", self.code)
return
end
self.grayCode(n - 1)
# Calculate gray code
self.code = self.code ^ (1 << (n - 1))
self.grayCode(n - 1)
end
# Handles the request to find gray code
def findGraycode(n)
if (n <= 0)
return
end
print("\n (", n ,") Bit gray code ")
self.code = 0
self.grayCode(n)
print("\n")
end
end
def main()
task = GenerateGrayCode.new()
n = 4
# Test when n = 4
task.findGraycode(n)
n = 5
# Test when n = 5
task.findGraycode(n)
end
main()
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
/*
Scala Program for
Generate n bit gray code
*/
class GenerateGrayCode(var code: Int)
{
def this()
{
this(0);
}
// Print gray code
def grayCode(n: Int): Unit = {
if (n == 0)
{
// Display calculate code
print("\n " + this.code);
return;
}
this.grayCode(n - 1);
// Calculate gray code
this.code = this.code ^ (1 << (n - 1));
this.grayCode(n - 1);
}
// Handles the request to find gray code
def findGraycode(n: Int): Unit = {
if (n <= 0)
{
return;
}
print("\n (" + n + ") Bit gray code ");
this.code = 0;
this.grayCode(n);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: GenerateGrayCode = new GenerateGrayCode();
var n: Int = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
/*
Swift 4 Program for
Generate n bit gray code
*/
class GenerateGrayCode
{
var code: Int;
init()
{
self.code = 0;
}
// Print gray code
func grayCode(_ n: Int)
{
if (n == 0)
{
// Display calculate code
print("\n ", self.code, terminator: "");
return;
}
self.grayCode(n - 1);
// Calculate gray code
self.code = self.code ^ (1 << (n - 1));
self.grayCode(n - 1);
}
// Handles the request to find gray code
func findGraycode(_ n: Int)
{
if (n <= 0)
{
return;
}
print("\n (", n ,") Bit gray code ", terminator: "");
self.code = 0;
self.grayCode(n);
print(terminator: "\n");
}
}
func main()
{
let task: GenerateGrayCode = GenerateGrayCode();
var n: Int = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
main();
Output
( 4 ) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
( 5 ) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
/*
Kotlin Program for
Generate n bit gray code
*/
class GenerateGrayCode
{
var code: Int;
constructor()
{
this.code = 0;
}
// Print gray code
fun grayCode(n: Int): Unit
{
if (n == 0)
{
// Display calculate code
print("\n " + this.code);
return;
}
this.grayCode(n - 1);
// Calculate gray code
this.code = this.code xor (1 shl(n - 1));
this.grayCode(n - 1);
}
// Handles the request to find gray code
fun findGraycode(n: Int): Unit
{
if (n <= 0)
{
return;
}
print("\n (" + n + ") Bit gray code ");
this.code = 0;
this.grayCode(n);
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var task: GenerateGrayCode = GenerateGrayCode();
var n: Int = 4;
// Test when n = 4
task.findGraycode(n);
n = 5;
// Test when n = 5
task.findGraycode(n);
}
Output
(4) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
(5) Bit gray code
0
1
3
2
6
7
5
4
12
13
15
14
10
11
9
8
24
25
27
26
30
31
29
28
20
21
23
22
18
19
17
16
Resultant Output Explanation
Let's analyze the output generated by the given code for n = 4 and n = 5.
For n = 4, the gray code sequence is:
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
Each number in the sequence differs from the previous number by only one bit, satisfying the property of Gray code.
Similarly, for n = 5, the gray code sequence is:
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16]
Again, each number in the sequence differs from the previous number by only one bit, following the rules of Gray code.
The time complexity of the given code is O(2^n), as each recursive call splits the problem into two subproblems, resulting in exponential growth.
Conclusion
In this article, we discussed the concept of generating n-bit Gray code. We explored a recursive approach to generate the Gray code sequence and provided a step-by-step explanation of the code. Additionally, we presented the resultant output for the test cases n = 4 and n = 5. Understanding and implementing Gray code can be useful in various applications where precise bit manipulation is required.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment