Gray Code to Binary Conversion

Problem Statement

Given a gray code, write a program to convert the given gray code to binary code.

• Gray code- It has a property in which two successive numbers differ from each other by only one bit.
• Binary code- It is a default way of storing numbers. It is represented in form of zeros and ones.

Example

• Given gray code- 110101
• Output after converting gray code to binary code- 100110

Example Explanation

In this, the MSB or the Most Significant Bit of the gray code will always be equal to the MSB of the binary code which in this case is 1.

For changing the other bits of the gray code to binary code, check the gray code bit at that index. If the bit of the current index of gray code is zero then copy the previous bit of binary code else if it’s one, then copy the inverted bit of the previous binary code.

Constraints

0<=N<=10⁸

Approach 1: Binary to Gray Conversion

Algorithm:

• Initialize graycode as empty
• Add to the graycode, the first binary bit
• Iterate through for loop and add to the graycode, the Xor of binary code at the current index and binary code of previous index.
• return the graycode.

Program for Converting Binary Code to Gray in C++

#include <iostream>
using namespace std;

// this is a helper function to xor two characters
char XorC(char x, char y) { return (x == y) ? '0' : '1'; }

// this is a helper function to flip the bit of the code
char flip(char z) { return (z == '0') ? '1' : '0'; }

// function to convert binary code to gray code
// code are i string format
string binarytoGray(string BinaryCode)
{
	string GrayCode = "";

	//here MSB of gray code is same as BinaryCode code
	GrayCode += BinaryCode[0];

	// Computing remaining bits, and next bit by doing XOR of previous and current in Binary code
	for (int i = 1; i < BinaryCode.length(); i++) {
		// Concatenate XOR of previous bit that of the current bit
		GrayCode += XorC(BinaryCode[i - 1], BinaryCode[i]);
	}

	return GrayCode;
}


int main()
{
	string BinaryCode = "01001";
	cout << "Gray code of " << BinaryCode << " is "
		<< binarytoGray(BinaryCode) << endl;

	}

Program to Convert Binary Code to Gray in Java

import java.io.*;
class Main
{

	// this is a helper function to xor  two characters
	char XorC(char x, char y)
	{
		return (x == y) ? '0' : '1';
	}

	// this is a helper function to flip the bit of the code
	char flip(char z)
	{
		return (z == '0') ? '1' : '0';
	}

	// function to convert binary string to gray string
	String binarytoGray(String binary)
	{
		String gray = "";

		// MSB of gray code is same as that of the binary code
		gray += binary.charAt(0);

		// Computing remaining bits, and next bit by doing XOR of previous
	
		for (int i = 1; i < binary.length(); i++)
		{

			// Concatenating XOR of previous bit with current bit
			gray += XorC(binary.charAt(i - 1),
						binary.charAt(i));
		}
	return gray;
	}

	
	public static void main(String args[])
		throws IOException
	{
		Main obj = new Main();
		String binary = "01001";
		System.out.println("Gray code of " +
						binary + " is " +
						obj.binarytoGray(binary));

		}
}

Program to Convert Binary Code to Gray using Python

def XorC(x, y):
	return '0' if(x == y) else '1';

# this is a helper function to flip the bit of the code
def flipFunc(c):
	return '1' if(z == '0') else '0';

# function to convert binary string
# to gray string
def binarytoGray(binary):
	gray = "";

	# MSB of gray code is the same as that of the binary code
	gray += binary[0];

	# Computing the remaining bits,and  next bit by doing XOR of previous
	# and current in Binary
	for i in range(1, len(binary)):
		
		# Concatenate XOR of previous bit with current bit
		gray += XorC(binary[i - 1],
					binary[i]);

	return gray;


# main code
binary = "01001";
print("Gray code of", binary, "is",
			binarytoGray(binary));

Output:

Gray code of 01001 is 01101

Complexity Analysis

Since there is one for loop running inside the function, the time complexity is O(n) and the variable gray is used to for storing the output and hence the space complexity is also O(n).

Time Complexity: O(n)

Space Complexity: O(n)

Approach 2: Gray to Binary Conversion

• Initialize the binary string to empty
• To the binary string, append the first bit of the gray code
• Iterate using for loop from 1 to length of gray code
  • If the current bit of gray code is 0, then append the previous bit of binary code to the binary code.
  • Else flip the previous bit of the binary code and append it to the binary code.

Program to Convert Gray to Binary Code in C++

#include <iostream>
using namespace std;

// this is a helper function to xor two characters
char xor_c(char x, char y) { return (x == y) ? '0' : '1'; }

// this is a helper function to flip the bit of the code
char flipFunc(char z) { return (z == '0') ? '1' : '0'; }

// function to convert gray code to binary code
string g2b(string gray)
{
	string binary = "";

	// MSB of binary code is same as gray code
	binary += gray[0];

	// Computing remaining bits
	for (int i = 1; i < gray.length(); i++) {
		// If current bit is 0, concatenate previous bit
		if (gray[i] == '0')
			binary += binary[i - 1];

		// Else, concatenate invertion of previous bit
		else
			binary += flipFunc(binary[i - 1]);
	}

	return binary;
}


int main()
{

	string gray = "01101";
	cout << "Binary code of " << gray << " is "
		<< g2b(gray) << endl;
	return 0;
}

Program to Convert Gray to Binary in Java

import java.io.*;
class Main {

	// Helper function to xor two characters
	char XorC(char x, char y)
	{
		return (x == y) ? '0' : '1';
	}

	// Helper function to flip the bit of the code
	char flip(char z)
	{
		return (z == '0') ? '1' : '0';
	}

// function to convert gray code string to binary string
	String graytoBinary(String gray)
	{
		String binary = "";

		// MSB of binary code is same as that of the gray code
		binary += gray.charAt(0);

		// Compute remaining bits pf the code
		for (int i = 1; i < gray.length(); i++)
		{
		
			// If current bit is 0, concatenate previous bit
			if (gray.charAt(i) == '0')
				binary += binary.charAt(i - 1);
		
		// Else, concatenate invert of previous bit
			else
				binary += flip(binary.charAt(i - 1));
		}

		return binary;
	}

	public static void main(String args[])
		throws IOException
	{
		Main obj = new Main();
		String gray = "01101";
		System.out.println("Binary code of " +
						gray + " is " +
						obj.graytoBinary(gray));
	}
}

Program to Convert Gray Code to Binary Code in Python

# this is a helper function to xor two characters
def XorC(x, y):
	return '0' if(x == y) else '1';

# this is a helper function to InvertCode the bit of the code
def InvertCode(z):
	return '1' if(z == '0') else '0';


# function to convert gray code string to binary code string
def Gray2Binary(gray):

	binary = "";

	# MSB of binary code is same as that of gray code
	binary += gray[0];

	# Compute remaining bits of the code
	for i in range(1, len(gray)):
		
		# If current bit is 0, then concatenate previous bit
		if (gray[i] == '0'):
			binary += binary[i - 1];

		# Else, concatenate inversion  of previous bit
		else:
			binary += InvertCode(binary[i - 1]);

	return binary;

# main code

gray = "01101";
print("Binary code of", gray, "is",
			Gray2Binary(gray));

Output:

Binary code of 01101 is 01001

Complexity Analysis

Since there is one for loop running inside the function, the time complexity is O(n) and the variable gray is used for storing the output hence the space complexity is also O(n).

Time Complexity: O(n)

Space Complexity: O(n)

Approach 3: Binary to Gray Using Bitwise Operators

Algorithm:

• Initialize a function that takes binary numbers as the parameter.
• Perform that calculation, right shift the bit, and Xor it with the original number, i.e, n^(n>>1).
• Return the calculated number.

Program to Convert Binary to Gray Using the Bitwise Operator In C++

#include <bits/stdc++.h>
using namespace std;
// function to convert binary code to gray
int greyConverter(int n) { return n ^ (n >> 1); }
// main
int main()
{
	int n = 3;
	cout << greyConverter(n) << endl;

	n = 9;
	cout << greyConverter(n) << endl;

	return 0;
}

Program to Convert Binary to Gray Using the Bitwise Operator in Java

public class Main {
// function to convert binary to gray
	public static int greyConverter(int n)
	{
		return n ^ (n >> 1);
	}

	// main
	public static void main(String[] args)
	{
		int n = 3;
		System.out.println(greyConverter(n));

		n = 9;
		System.out.println(greyConverter(n));
	}
}

Program to Convert Binary to Gray Using the Bitwise Operator in Python

// function to convert binary to gray
def greyConverter(n):

	return n ^ (n >> 1)


n = 3
print(greyConverter(n))

n = 9
print(greyConverter(n))

Output:

2
13

Complexity Analysis

Since there is no loop, the approach using bitwise operator is much faster and takes no space for storing the output.

Time Complexity: O(1)

Space Complexity: O(1)

Approach 4: Gray to Binary Using Bitwise Operators

Algorithm:

• Initialize the result as the number given by the user.
• Run a while loop till n > 0 and perform the following:
  • Right shift the number by 1
  • Xor the number with the result
• Return the result

Program To Convert Gray To Binary In C++

#include <bits/stdc++.h>
using namespace std;
// binary converter function
int binaryConverter(int n)
{
	int res = n;
	while (n > 0)
	{
		n >>= 1;
		res ^= n;
	}
	return res;
}

// Main Code
int main()
{
	int n = 4;

	// Function call
	cout << binaryConverter(n) << endl;

	return 0;
}

Program to Convert Gray to Binary in Java

public class Main {
// method to convert gray to binary
	public static int binaryConverter(int n)
	{
		int res = n;

		while (n > 0) {
			n >>= 1;
			res ^= n;
		}

		return res;
	}

	// main code
	public static void main(String[] args)
	{
		int n = 4;
		System.out.println(binaryConverter(n));
	}
}

Program to Convert Gray to Binary in Python

# function to convert gray to binary
def binaryConverter(n):
	res = n

	while n > 0:
		n >>= 1
		res ^= n

	return res

# main
n = 4
print(binaryConverter(n))

Output:

7

Complexity Analysis

Since there is just one loop and n is being right shifted in every iteration, the approach using bitwise operator is much faster and takes no space for storing the output.

Time Complexity: O(log(n))

Space Complexity: O(1)

Conclusion

• Gray code- it has a property in which two successive numbers differ from each other by only one bit.
• Binary code- it is a default way of storing numbers. It is represented in form of zeros and ones.
• Explanation of gray to binary conversion:
  • In this, the MSB or the Most Significant Bit of the gray code will always be equal to the MSB of the binary code.
  • For changing the other bits of the gray code to binary code, check the gray code bit at that index. If the bit of the current index of gray code is zero then copy the previous bit of binary code else if it’s one, then copy the inverted bit of the previous bit of binary code.