Gray Code#6005
A Gray code is a binary numbering system where two successive values differ only in one bit position. Each value in an -bit Gray code has bits. The most obvious case is for N = 1, when the Gray code values are just and .
If we have a list of the -bit Gray code values, then the N+1-bit Gray code can be obtained relatively simply. List the existing values in a column, draw a line under the last value, and "reflect" the existing values below the line. That is, duplicate the list in the opposite order. Then add a bit in front of the original values and a bit in front of the new "reflected" values. (Incidentally, this is why the Gray code is also called the "reflected binary code.")
For example, here is an illustration showing how we might generate the Gray code for N = 2:
So the list of Gray codes for N = 2 is , , , and .
Here is how we might generate the Gray code for N = 3:
Your task in this problem is to compute and display only the -th value in the -bit Gray code, suitably labeled. Assume the values are numbered starting with . So if N = 3 and k = 4 your program will display .
The Java BigInteger class may not be used in a solution to this problem.
There will be multiple input cases. For each case, the input will consist of a single line containing integer values for and separated by one or more blanks and followed by an end of line character. will be between and , and will be between and 2^N-1. The line following the input line for the last case will contain two zeroes.
If it isn't immediately obvious from the preceding text, note that the value of may not fit in a bit or even a bit integer. It should also be noted that you will not want to compute all 2^N gray code values, but focus your attention on the computation of only the -th such value.
For each input case display the case number (, , …), the values of and , and the -th Gray code value (labeled as ""). Follow the format shown in the samples below.
Example 1