Gray to Binary

How to convert Binary to Gray Code?

Now, we will discuss how to convert the binary code to gray code. There are 3 basic steps in order to convert a binary to gray code:

1. Record the Most Significant Bit (MSB) of binary code as it is.
    
2. Add the MSB to the next bit of the binary code, record the sum, and neglect the carry.
   In the 2nd step, the XOR operation can also be done instead of adding MSB to the next bit and neglecting the carry.
    
3. Repeat step 2 again till the end of the binary code.

Here’s the XOR truth table below to check the results:

Here’s an example to understand the conversion:

How to convert Gray Code to Binary?

There are 3 basic steps in order to convert a gray to binary code:

1. Record the Most Significant Bit (MSB) of gray code as it is. 
2. Perform XOR operation between MSB and the next bit of gray code.
3. Repeat step 2 again till the end of the gray code.

Here’s the XOR truth table below to check the results:

Here’s an example to understand the conversion:

Code for Gray to Binary

1st Approach

We will iterate the given gray string, and firstly we will add the MSB of gray code to our answer binary, and from 1st index to n (length of gray), we will be doing a computation basis on the current digit. If the current digit is 0, without any computation, 0 can be written in the answer, and If the current digit is 1, we have to check if the previous digit is 0 or 1. You can easily understand this computation by the comments in the code.

C++

#include <iostream>
using namespace std;

string grayToBinary(string gray)
{
	// storing length of gray in n
	int n = gray.size();

	// starting with an empty string, that will be our answer.
	string binary = "";

	// adding MSB of gray to answer as it is.
	binary += gray[0];

	// iterating till the length of gray.
	for (int i = 1; i < n; i++) {
	
		// If the digit is 0, copying the previous digit to answer
		if (gray[i] == '0')
			binary += binary[i - 1];
			
		/*	
		   If the digit is 1, then we have to check if previous digit 0 or 1,
		   if the previous digit is 1, then 0 because 1 ⊕ 0 = 0
		   else 1 because 1 ⊕ 1 = 0
		*/
		else {
			if (binary[i - 1] == '0')
				binary += '1';
			else
				binary += '0';
		}
	}
	return binary;
}

int main() {
	string gray;
	cout << "Hey Ninja, Please enter a gray code: ";
	cin >> gray;
	cout << "Binary Code: " << grayToBinary(gray) << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Scanner;

public class Main {
	public static String grayToBinary(String gray) {
		// storing length of gray in n
		int n = gray.length();
		
		// starting with an empty string, that will be our answer.
		String binary = "";
		
		// adding MSB of gray to answer as it is.
		binary += gray.charAt(0);
		
		// iterating till the length of gray.
		for (int i = 1; i < n; i++) {
		
			// If the digit is 0, copy the previous digit to answer
			if (gray.charAt(i) == '0')
				binary += binary.charAt(i - 1);
				
			/*	
		   		If the digit is 1, then we have to check if previous digit 0 or 1,
		   		if the previous digit is 1, then 0 because 1 ⊕ 0 = 0
		   		else 1 because 1 ⊕ 1 = 0
			*/	
			
			else {
				if (binary.charAt(i - 1) == '0')
					binary += '1';
				else
					binary += '0';
			}
		}
		return binary;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.print("Hey Ninja, Please enter a gray code: ");
		String gray = scanner.nextLine();
		System.out.println("Binary Code: " + grayToBinary(gray));
	}
}

You can also try this code with Online Java Compiler

Run Code

Python

def grayToBinary(gray):
    # storing length of gray in n
    n = len(gray)
    
    # starting with an empty string, that will be our answer.
    binary = ""
    
    # adding MSB of gray to answer as it is.
    binary += gray[0]
    
    # iterating till the length of gray.
    for i in range(1, n):
    
        # If the digit is 0, copy the previous digit to answer,
        if gray[i] == '0':
            binary += binary[i - 1]
            
         """   
          	If the digit is 1, then we have to check if previous digit 0 or 1,
          	if the previous digit is 1, then 0 because 1 xor 0  = 0
          	else 1 because 1 xor 1 = 0 
         """
        else:
            if binary[i - 1] == '0':
                binary += '1'
            else:
                binary += '0'
    return binary


gray = input("Hey Ninja, Please enter a gray code: ")
print("Binary Code: " + grayToBinary(gray))

You can also try this code with Online Python Compiler

Run Code

Output:

Hey Ninja, Please enter a gray code : 1000
Binary Code: 1111

Time Complexity:

Here n is the size of the given gray string.

There is an iteration of the gray string, which takes 1 to n iterations. So Overall Time Complexity is O(n).

Space Complexity:

A string of the answer (binary) is stored in the memory of size n. So Space Complexity is also O(n).

2nd Approach

This is an easier and optimal approach to convert the gray code to binary code. In this approach, a gray number will be input, and bitwise operators will be used by which we will right shift the bit in the given gray number, and we will xor the digit in the gray number with the given gray number itself so that no  Auxiliary memory is needed to be used.

C++

#include <bits/stdc++.h>
using namespace std;

int grayToBinary(int gray) {

   /*
		 Here, we are doing right shift the bits in given gray number and
		 doing xor(^) operation with the given gray number.
		 Returning the result automatically after the gray number ends.
   */
   
	return gray ^ (gray >> 1);
}

int main() {
	int gray;
	cout << "Hey Ninja, Please enter a gray number: ";
	cin >> gray;
	cout << "Binary Number: " << grayToBinary(gray) << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Scanner;

public class Main {
    public static int grayToBinary(int gray) {
    
    /*
       Here, we are doing right shift the bits in the given gray number and
       doing xor(^) operation with the given gray number.
       Returning the result automatically after the gray number ends.
    */
    return gray ^ (gray >> 1);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Hey Ninja, Please enter a gray number: ");
        int gray = scanner.nextInt();
        System.out.println("Binary Number: " + grayToBinary(gray));
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def grayToBinary(gray):
    """
    	Here, we are doing right shift the bits in the given gray number and
    	doing xor(^) operation with the given gray number.
    	Returning the result automatically after the gray number ends.
    """
    return gray ^ (gray >> 1)

gray = int(input("Hey Ninja, Please enter a gray number: "))
print("Binary Number: ", grayToBinary(gray))

You can also try this code with Online Python Compiler

Run Code

Output:

Hey Ninja enter a gray number : 3
Binary Number: 2

Time Complexity:

In this approach, There are no iterations, and bitwise operators are fast. So, The Overall Time Complexity is O(1).

Space Complexity:

Only a gray number is inputted, which is an integer that takes constant space. So, The Space Complexity is O(1).

Pros of Gray Code

• Gray Codes can be easily converted by using basic binary manipulations (XOR).
   
• Gray Codes help in reducing the chances of errors as only a bit changes at a time, unlike binary code.
   
• Gray Codes can be used in rotary encoders as gray codes provide accurate positioning.
   
• Gray codes can also be used to reduce the glitches in circuits.

Cons of Gray Code

• Gray Codes can be challenging sometimes to understand and interpret.
   
• Arithmetic Operations such as addition and subtraction can be inefficient in gray codes. Before doing these operations, gray codes should be converted to binary.
   
• Implementing gray codes in the circuit can be complex because extra logic should be provided to convert the gray to binary code.

 Also see, Rabin Karp Algorithm

Frequently Asked Questions

What is GRAY code in binary?

Gray code is a sequence of binary numbers known as reflected binary code (RBC). Gray code was introduced by Frank Gray. In gray code, two successive values differ by only 1 bit. Conversion of binary codes to gray codes results in reducing the switching operations.

Which gate is used in Gray to binary conversion?

In Gray to binary conversion, the exclusive OR (XOR) gate is typically used to calculate each bit of the binary number from the corresponding Gray code bit.

What is convert binary number into gray code 100101?

To convert a binary number (100101) into Gray code, exclusive OR (XOR) each bit with the previous bit's value. The Gray code for 100101 is 110111.

Conclusion

Gray code is a sequence of binary numbers known as reflected binary code (RBC). Gray code was introduced by Frank Gray. In this blog, we discussed what gray codes are and how to convert between binary to gray and gray to binary. We also discussed the pros and cons of gray codes. After understanding how to convert gray to binary, we code this conversion practically in multiple languages such as C++, Java, and Python. I hope you understood everything theoretically and programmatically about the conversion between gray to binary codes.

Do check out The Interview Guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc., on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.