by Jason Menard
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 2n 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 (23) 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:
Integer BRGC
======= ====
0 0
1 1
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:
Integer BRGC
======= ====
0 00
1 01
2 11
3 10
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:
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
Looking that the chart above tells us that the BRGC encoding for the integer 7 is 100.
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:
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
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.
See the thread August Newsletter Puzzle in the Programming Diversions forum to post your answer and discuss this problem.