C++ program to convert binary number to Gray code using recursion

Gray code or reflected binary code is a special type of binary representation of a number in which two consecutive values ​​differ in only one bit. For example, the binary equivalents of 1 and 2 are 01 and 10, where two bits are changing. But in Gray code, 1 is 01, 2 is 11, and only one bit is changing. In this article, we will see how to convert a given binary number to its Gray code equivalent using recursion in C.

Pass numbers as decimal integers

In the first example, we provide decimal numbers. The numbers are only 0 and 1, but the numbers are in decimal. For example, if we want to pass 6 as input, we pass 110 (one hundred and ten in decimal), which is equivalent to 6 in binary. The program returns output similarly.

algorithm

• Define a function solve(), which will take a binary number
• If n is 0, then
  • Return 0
• If it ends
• Last := the last digit of n
• second_last = the penultimate digit of n
• If the last digit and the penultimate digit are different, then
  • Enter 1 and call solve(n cuts the last bit)
• otherwise
  • Enter 0 and call solve(n cuts the last bit)
• If it ends
• solve() function ends

Example

#include <iostream>
using namespace std;

int solve( int n ) {
   if( n == 0 )
   return 0;
   int last = n % 10;
   int second_last = (n / 10) % 10;
   if( (last && !second_last) || (!last && second_last) ) {
      return (1 + 10 * solve( n / 10 ));
   }
   return (10 * solve( n / 10 ));
}

int main()
{
   cout << "Gray code for the number 2 (10) is: " << solve( 10 ) << endl;
   cout << "Gray code for the number 6 (110) is: " << solve( 110 ) << endl;
   cout << "Gray code for the number 13 (1101) is: " << solve( 1101 ) << endl;
   cout << "Gray code for the number 93 (1011101) is: " << solve( 1011101 ) << endl;
}

Output

Gray code for the number 2 (10) is: 11
Gray code for the number 6 (110) is: 101
Gray code for the number 13 (1101) is: 1011
Gray code for the number 93 (1011101) is: 1110011

in conclusion

Gray code or reflected binary code can be found by applying XOR operation to consecutive bits. The same thing is achieved by taking the last two digits of the given number, when they are not the same, call the function recursively and pass the number except the last digit, the result will be concatenated with 1, otherwise with 0, etc. And so on. In the example, we have provided input as an integer decimal number and the output is also in integer decimal format. The same problem can be solved by taking a string type input which can be used to provide larger input when required.

The above is the detailed content of C++ program to convert binary number to Gray code using recursion. For more information, please follow other related articles on the PHP Chinese website!