Python 格雷碼轉換公式 i^i//2，簡潔優美 pythonic

格雷碼 Gray Code

是一種二進制數字系統，其中任意兩個相鄰的連續值僅有一個二進位不同，包括頭尾兩數也只有一位不同，若不明白或者說沒有接觸過GrayCode，請去網上搜索更詳細的概念說明……

異或轉換

最高位不變，從第二位起每一位都是與前一位的異或結果，

一個整數右移一位再和自身異或剛好滿足轉換要求，如下代碼非常的簡短優美，return運算式中不用括號是因為>>和//的運算優先級都高于^異或運算，

def N2G(i):
    return i^i>>1

# (或者i^i//2，兩者等價)

輸出二進制的格雷碼：

>>> def N2G(i):
	return bin(i^i>>1)[2:]

卡諾圖

是邏輯函式的一種圖形表示，它也和格雷碼有關聯，在 Karnaugh map 上不僅左右相鄰的、每行或列首尾的，就連矩陣中的上下相鄰的、鏡像對應的也都只有一個二進位上不同，以下是二到五變數卡諾圖：

目前在百度圖片中搜索“卡諾圖”，還能搜到許多用紅綠橙等多色圈注過的卡諾圖，這些大都是我在百度知道上答題所上傳的，（有點自炫自嗨了^_^）

刷題實戰 Leetcode#89

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 equence of gray code. A gray code sequence must begin with 0.

Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1

Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].

題意：給定表示二進制碼中總位數的非負整數n，列印以0開頭的格雷碼序列，

方法一： 格雷碼轉換公式 i^i>>1 , 看上去很優美，

>>> Gray = lambda n:[i^i>>1 for i in range(2**n)]
>>> Gray(0)
[0]
>>> Gray(1)
[0, 1]
>>> Gray(2)
[0, 1, 3, 2]
>>> Gray(3)
[0, 1, 3, 2, 6, 7, 5, 4]
>>> Gray(4)
[0, 1, 3, 2, 6, 7, 5, 4,
 12, 13, 15, 14, 10, 11, 9, 8]
>>> Gray(5)
[0, 1, 3, 2, 6, 7, 5, 4,
 12, 13, 15, 14, 10, 11, 9, 8,
 24, 25, 27, 26, 30, 31, 29, 28,
 20, 21, 23, 22, 18, 19, 17, 16]
>>> # 與卡諾圖的數字對比一下

改進一下，以二進制格式輸出：

>>> GrayB = lambda n:[bin(i^i//2)[2:].rjust(n,'0') for i in range(2**n)]
>>> GrayB(0)
['0']
>>> GrayB(1)
['0', '1']
>>> GrayB(2)
['00', '01', '11', '10']
>>> GrayB(3)    # 把輸出排成矩陣，與三變數卡諾圖對比一下
['000', '001', '011', '010',
 '110', '111', '101', '100']
>>> GrayB(4)    # 把輸出排成方陣，與四變數卡諾圖對比一下
['0000', '0001', '0011', '0010',
 '0110', '0111', '0101', '0100',
 '1100', '1101', '1111', '1110',
 '1010', '1011', '1001', '1000']
>>> GrayB(5)    # 把輸出排成矩陣，與五變數卡諾圖對比一下
['00000', '00001', '00011', '00010', '00110', '00111', '00101', '00100',
 '01100', '01101', '01111', '01110', '01010', '01011', '01001', '01000',
 '11000', '11001', '11011', '11010', '11110', '11111', '11101', '11100',
 '10100', '10101', '10111', '10110', '10010', '10011', '10001', '10000']
>>> 

方法二：迭代法，兩行代碼，這種寫法算不算首創，反正我沒見過相同的代碼，再次自炫自嗨中^_^

>>> def iGray(n):
	if n==0: return [0]
	return iGray(n-1)+[i+2**(n-1) for i in iGray(n-1)[::-1]]

>>> iGray(0)
[0]
>>> iGray(1)
[0, 1]
>>> iGray(2)
[0, 1,
 3, 2]
>>> iGray(3)
[0, 1, 3, 2,
 6, 7, 5, 4]
>>> iGray(4)
[0, 1, 3, 2, 6, 7, 5, 4, 
12, 13, 15, 14, 10, 11, 9, 8]
>>> 

這個迭代法沒有用到異或運算，就是按照數字出現的規律來推導的，原理：函式F(n)，n>0時輸出的串列，其后半段反轉后的各元素與前半段各元素對應位置的差值都相等，剛好是2的(n-1)次方，

反查串列驗證測驗：

函式：N2Gray(n,m=0)
引數：n為待轉換非負整數；m為輸出寬度(二進制位數)，默認所有前導的0都省略，

>>> def N2Gray(n,m=1):
	t=0
	while n+1>2**t: t+=1
	return [bin(i^i//2)[2:].rjust(t,'0') for i in range(2**t)][n].rjust(m,'0')

>>> for i in range(20):
	print(i,N2Gray(i))

	
0 0
1 1
2 11
3 10
4 110
5 111
6 101
7 100
8 1100
9 1101
10 1111
11 1110
12 1010
13 1011
14 1001
15 1000
16 11000
17 11001
18 11011
19 11010
>>>
>>> N2Gray(8)
'1100'
>>> N2Gray(8,5)
'01100'
>>> N2Gray(8,6)
'001100'
>>> 

十進制數和二進制格雷碼互轉

十進制數轉二進制格雷碼：

>>> def N2G(n,m=1):
	return bin(n^n>>1)[2:].rjust(m,'0')

>>> N2G(12)
'1010'
>>> N2G(12,5)
'01010'
>>> N2G(12,6)
'001010'
>>> 

二進制格雷碼轉十進制數：

>>> def G2N(G):
	for i in range(2**len(G)):
		if G==bin(i^i>>1)[2:]:break
	return i

>>> G2N('0')
0
>>> G2N('1')
1
>>> G2N('10')
3
>>> G2N('11')
2
>>> G2N('101')
6
>>> G2N('1010')
12
>>> G2N('11010')
19
>>> 

(本篇完)