格雷码 Gray Code
是一种二进制数字系统,其中任意两个相邻的连续值仅有一个二进位不同,包括头尾两数也只有一位不同。若不明白或者说没有接触过GrayCode,请去网上搜索更详细的概念说明……
异或转换
最高位不变,从第二位起每一位都是与前一位的异或结果。
一个整数右移一位再和自身异或刚好满足转换要求,如下代码非常的简短优美。return表达式中不用括号是因为>>和//的运算优先级都高于^异或运算。
1. def N2G(i): 2. return i^i>>1 3. 4. # (或者i^i//2,两者等价)
输出二进制的格雷码:
1. >>> def N2G(i): 2. 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 >>>
(本篇完)