LeetCode --- 89. 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.

           

解析

這道題的要求是按順序生成所有n位格雷碼。

在一組數的編碼中，若任意兩個相鄰的代碼隻有一位二進制數不同，則稱這種編碼為格雷碼（Gray Code），另外由于最大數與最小數之間也僅一位數不同，即“首尾相連”，是以又稱循環碼或反射碼。在數字系統中，常要求代碼按一定順序變化。例如，按自然數遞增計數，若采用8421碼，則數0111變到1000時四位均要變化，而在實際電路中，4位的變化不可能絕對同時發生，則計數中可能出現短暫的其它代碼（1100、1111等）。在特定情況下可能導緻電路狀态錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。格雷碼有多種編碼形式。

格雷碼（Gray Code）曾用過Grey Code、葛萊碼、格萊碼、戈萊碼、循環碼、反射二進制碼、最小差錯碼等名字，它們有的不對，有的易與其它名稱混淆，建議不要再使用這些曾用名。

直接排列

以二進制為0值的格雷碼為第零項，第一項改變最右邊的位元，第二項改變右起第一個為1的位元的左邊位元，第三、四項方法同第一、二項，如此反複，即可排列出n個位元的格雷碼。

鏡射排列

n位元的格雷碼可以從n-1位元的格雷碼以上下鏡射後加上新位元的方式快速的得到。這種方法基于格雷碼是反射碼的事實，利用遞歸的如下規則來構造：

1位格雷碼有兩個碼字
(n+1)位格雷碼中的前2^n個碼字等于n位格雷碼的碼字，按順序書寫，加字首0
(n+1)位格雷碼中的後2^n個碼字等于n位格雷碼的碼字，按逆序書寫，加字首1
           

二進制數轉格雷碼

（假設以二進制為0的值做為格雷碼的0）

G：格雷碼 B：二進制碼

G(N) = (B(n)/2) XOR B(n)

格雷碼轉二進制數

二進制碼第n位 = 二進制碼第（n+1）位+格雷碼第n位。因為二進制碼和格雷碼皆有相同位數，是以二進制碼可從最高位的左邊位元取0，以進行計算。（注：遇到1+1時結果視為0）

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

0+0=0，是以b3=0

0+1=1，是以b2=1

1+1取0，是以b1=0

0+1取1，是以b0=1

是以所轉換為之二進制碼為0101。

C/C++基本文法學習

STL

C++ primer