[leetcode](Gray Code 格雷碼 C語言實作)

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0

01 - 1

11 - 3

10 - 2

Note:

For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

gary code(格雷碼)：參照百度百科，

公式表示：

（G：格雷碼，B：二進制碼）

例如：二進制碼0101，為4位數，是以其所轉為之格雷碼也必為4位數，是以可取轉成之二進位碼第五位為0，即0 b3 b2 b1 b0。

0 xor 0=0，是以g3=0

0 xor 1=1，是以g2=1

1 xor 0=1，是以g1=1

0 xor 1=1，是以g0=1

是以所轉換為之格雷碼為0111

實作C代碼如下：

/**解題思路：gray code 滿足Gi = Bi^B(i+),把二進制碼轉換為gray碼：即從右到左，倒數第一位與倒數第二位進行異或，得到gray碼的倒數第一位，依次比較下去，并把二進制碼的第一位原樣輸出作為gray碼的第一位。
 * 例如：
 *              二進制碼        gray code
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 *                  ->        
 * Definition for an integer array.
 * struct IntArray {
 *     int* elements;
 *     int size;
 * };
 */
struct IntArray* grayCode(int n) {
    struct IntArray *p;
    int i,temp;
    p = (struct IntArray *)malloc(sizeof(struct IntArray));
    p->size = ;
    for(i=;i<n;i++){
        p->size *= ;
    }
    p->elements = (int *)malloc(p->size*sizeof(int));
    memset(p->elements,,sizeof(p->elements));
    for(i=;i<p->size;i++){
        temp = i;
        p->elements[i] = (i>>)^temp;//實作異或
    }
    return p;
}