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
>>> 

 (本篇完)