Problem I
Grey Codes
Input: Standard Input

Output: Standard Output

Bill Cosby

We are going to generate a sequence of integers in binary. Start with the sequence

Reflect it in the horizontal line, prepend a zero to the numbers in the top half and a one to the numbers on the bottom and you will get

Repeat this again, and you will have 8 numbers

The corresponding decimal values are shown on the right.

These sequences are called Reflected Gray Codes for 1, 2 and 3 bits respectively. A Gray Code for n bits is a sequence of 2ⁿ different n-bit integers with the property that every two neighbouring integers differ in exactly one bit. A Reflected Gray Code is a Gray Code constructed in the way shown above.

Input

The first line of input gives the number of cases, N (at most 250000). N test cases follow. Each one is a line with 2 integers: n (1 <= n <= 30) and k (0 <= k < 2ⁿ).

Output

For each test case, output the integer that appears in position k of the n-bit Reflected Gray Code.

Sample Input                                  Output for Sample Input

14

1 0

1 1

2 0

2 1

2 2

2 3

3 0

3 1

3 2

3 3

3 4

3 5

3 6

3 7

0

1

0

1

3

2

0

1

3

2

6

7

5

4

Problem setter: Igor Naverniouk

遞迴就是用一半去看，遞迴應該不難理解才是。

#include <stdio.h>
int N2[32];
int grey(int n, int k) {
    if(n == 0)  return 0;
    if(k >= N2[n-1])
        return N2[n-1]|(grey(n-1, N2[n]-k-1));
    else
        return grey(n-1, k);
}
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, k, t;
    for(n = 0; n <= 31; n++)
        N2[n] = 1<<n;
    ReadInt(&t);
    while(t--) {
        ReadInt(&n);
        ReadInt(&k);
        printf("%d\n", grey(n, k));
    }
    return 0;
}