# August Newsletter Puzzle

Jason Menard

Sheriff

Posts: 6450

posted 13 years ago

<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<sup>n</sup> 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<sup>3</sup>) 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:

Calling the method...

...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:

Calling the method...

...should display

The third method returns the long integer representation of an input BRGC encoding.

It should have the following signature...

Calling the method...

...should display

<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<sup>n</sup> 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<sup>3</sup>) 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.
Roy Tock

Ranch Hand

Posts: 83

posted 13 years ago

I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

Jason Menard

Sheriff

Posts: 6450

posted 13 years ago

No, not really. You aren't required to display leading zeroes. The answer for encode(5) will always be "111" for example, as opposed to "0111", "00111" or the like. But if it helps to think about it like this, keep in mind that the standard binary representation of 5 requires three bits, so the BRGC encoded representatin of 5 also requires three bits.

[ August 03, 2003: Message edited by: Jason Menard ]

Originally posted by Roy Tock:

I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

No, not really. You aren't required to display leading zeroes. The answer for encode(5) will always be "111" for example, as opposed to "0111", "00111" or the like. But if it helps to think about it like this, keep in mind that the standard binary representation of 5 requires three bits, so the BRGC encoded representatin of 5 also requires three bits.

[ August 03, 2003: Message edited by: Jason Menard ]

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 13 years ago

You can write the Gray codes for n bits into a grid so that when you move from one cell to another in NSEW directions only one bit changes - wrap around from one edge to the opposite edge. I wonder if that's at all tricky to automate.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

Roy Tock

Ranch Hand

Posts: 83

David Weitzman

Ranch Hand

Posts: 1365

Michael Zalewski

Ranch Hand

Posts: 168

posted 13 years ago

There is a very neat property of Gray Codes

You can translate from Gray Code to Binary by realizing that a '1' in Gray code means that the corresponding digit in binary code is different from the one immediately to the left. A '0' in Gray code means the corresponding binary digit is the same.

You can translate from Gray Code to Binary by realizing that a '1' in Gray code means that the corresponding digit in binary code is different from the one immediately to the left. A '0' in Gray code means the corresponding binary digit is the same.

Fintan Conway

Ranch Hand

Posts: 142

posted 13 years ago

Hi All,

This code works by using the number of bits to run a recursive method. In using the previous values to create the current values it stores the previous value in 2 places adding the "0" in front of one, and "1" in front of another. The resulting BRGC is stored in an array and printed; solving problem (a).

(b) To find the BRGC of a particular number it calculates the number of bits by converting the number to a Binary String (Long.toBinaryString(y) ) and creates the array using the solution to (a). It then looks up the BRGC corresponding to the correct index.

(c) To find the number corresponding to the BRGC, we already have the number of bits, create the array and search it (Arrays.binarySearch) to give the right index.

Regards,

Fintan

[ August 11, 2003: Message edited by: Fintan Conway ]

[ August 11, 2003: Message edited by: Fintan Conway ]

This code works by using the number of bits to run a recursive method. In using the previous values to create the current values it stores the previous value in 2 places adding the "0" in front of one, and "1" in front of another. The resulting BRGC is stored in an array and printed; solving problem (a).

(b) To find the BRGC of a particular number it calculates the number of bits by converting the number to a Binary String (Long.toBinaryString(y) ) and creates the array using the solution to (a). It then looks up the BRGC corresponding to the correct index.

(c) To find the number corresponding to the BRGC, we already have the number of bits, create the array and search it (Arrays.binarySearch) to give the right index.

Regards,

Fintan

[ August 11, 2003: Message edited by: Fintan Conway ]

[ August 11, 2003: Message edited by: Fintan Conway ]

Jason Menard

Sheriff

Posts: 6450

posted 13 years ago

Here's my solution... No arrays were explicitly used.

I used an algorithm for my encode that is simple enough I could have done the whole method in one line. Simply take the unencoded decimal value, use integer division to divide it by 2, and XOR that value with the unencoded decimal value. Then just convert the resulting decimal to binary to get your BRGC encoding.

For my display() method, I simply called encode() and padded the result with the appropriate number of zeroes prefixed.

Since there's a simple equation to encode a number into BRGC, I would think there might also be an equation to decode as well. Anyone have any idea on this? Not knowing an easy way to decode, I used the algorithm Michael Zalewski mentioned but implemented it quite differently than he did, prefering mathematical bit manipulation to character manipulation.

I used an algorithm for my encode that is simple enough I could have done the whole method in one line. Simply take the unencoded decimal value, use integer division to divide it by 2, and XOR that value with the unencoded decimal value. Then just convert the resulting decimal to binary to get your BRGC encoding.

For my display() method, I simply called encode() and padded the result with the appropriate number of zeroes prefixed.

Since there's a simple equation to encode a number into BRGC, I would think there might also be an equation to decode as well. Anyone have any idea on this? Not knowing an easy way to decode, I used the algorithm Michael Zalewski mentioned but implemented it quite differently than he did, prefering mathematical bit manipulation to character manipulation.