Skip to main content

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.

Last updated on by Kalkicode




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.

New Comment