<h3>Binary Reflected Gray Code</h3>
<h4>Background</h4>
A Gray code is an ordered set of binary numbers such that only one bit changes
from one element to the next. Any n-bit Gray code will have 2
^{n} elements.
{000, 001, 011, 010, 110, 111, 101, 100} and {000, 010, 011, 001, 101, 100,
110, 111} are both examples of 3-bit Gray codes. Note that only one bit changes
between each element and each set has 8 (2
^{3}) elements.
A binary reflected Gray code (BRGC) is a particular encoding for non-negative
integers. To find a BRGC of n bits, take the BRGC of ( n - 1 ) bits, writing
it forward and then backward. Prefix the first half of the binary numbers with
0, and prefix the second half of the binary numbers with 1. The binary reflected
Gray code of 1 bit (integer values 0 and 1) is:
<pre>
Integer BRGC
======= ====
0 0
1 1
</pre>
To find the BRCG up through 2-bit integers (0, 1, 2, 3), write the BRCG of 1 bit
going forward (0, 1), then backwards (1, 0), to get (0, 1, 1, 0). Prefix the first
half of those numbers with 0 and the second half with 1, giving us:
<pre>
Integer BRGC
======= ====
0 00
1 01
2 11
3 10
</pre>
Looking at the above chart we came up with, we can see that the BRCG encoding for the integer 2 is 11.
Let's try it one more time, finding the BRCG for integers up to 3-bits (0, 1, 2, 3, 4, 5, 6, 7). First we write the 2 bit BRGC forward then backwards (00, 01, 11, 10, 10, 11, 01, 00). Finally we prefix the first half of those numbers with 0, and the second half with 1:
<pre>
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
</pre>
Looking that the chart above tells us that the BRGC encoding for the integer
7 is 100.
<h4>The Challenge</h4>
Write a class BRGC containing three static methods. The first method displays
a table of long integers and their BRGC encoded values up to n-bits. It should
have the following signature:
public static void displayBRCG(long n) Calling the method...
BRGC.displayBRGC(3); ...should produce something similar to the following output:
<pre>
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
</pre>
The second method returns the BRGC encoded representation of an input non-negative
long integer. It should have the following signature:
public static String encode(long n) Calling the method...
System.out.println(BRGC.encode(5)); ...should display
111 on the console.
The third method returns the long integer representation of an input BRGC encoding.
It should have the following signature...
public static long decode(String brgc) Calling the method...
System.out.println(BRGC.decode("111")); ...should display
5 on the console.