# 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)
{
int n = 4;
// Test when n = 4
n = 5;
// Test when n = 5
}
}``````

#### 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()
{
int n = 4;
// Test when n = 4
n = 5;
// Test when n = 5
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)
{
int n = 4;
// Test when n = 4
n = 5;
// Test when n = 5
}
}``````

#### 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()
{
\$n = 4;
// Test when n = 4
\$n = 5;
// Test when n = 5
}
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 n = 4;
// Test when n = 4
n = 5;
// Test when n = 5
}
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() :
n = 4
#  Test when n = 4
n = 5
#  Test when n = 5

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_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()
n = 4
#  Test when n = 4
n = 5
#  Test when n = 5
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
n = 5;
// Test when n = 5
}
}``````

#### 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()
{
var n: Int = 4;
// Test when n = 4
n = 5;
// Test when n = 5
}
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 n: Int = 4;
// Test when n = 4
n = 5;
// Test when n = 5
}``````

#### 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.

## Comment

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.