Python 格雷码转换公式 i^i//2,简洁优美 pythonic

简介: Python 格雷码转换公式 i^i//2,简洁优美 pythonic

格雷码 Gray Code

是一种二进制数字系统,其中任意两个相邻的连续值仅有一个二进位不同,包括头尾两数也只有一位不同。若不明白或者说没有接触过GrayCode,请去网上搜索更详细的概念说明……



异或转换

最高位不变,从第二位起每一位都是与前一位的异或结果。


20210818134324822.png


一个整数右移一位再和自身异或刚好满足转换要求,如下代码非常的简短优美。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 上不仅左右相邻的、每行或列首尾的,就连矩阵中的上下相邻的、镜像对应的也都只有一个二进位上不同。以下是二到五变量卡诺图:

20210818141403958.png

目前在百度图片中搜索“卡诺图”,还能搜到许多用红绿橙等多色圈注过的卡诺图,这些大都是我在百度知道上答题所上传的。(有点自炫自嗨了^_^)

 


刷题实战 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
>>> 

(本篇完)

目录
相关文章
|
6月前
|
数据采集 JSON API
如何实现高效率超简洁的实时数据采集?——Python实战电商数据采集API接口
你是否曾为获取重要数据而感到困扰?是否因为数据封锁而无法获取所需信息?是否因为数据格式混乱而头疼?现在,所有这些问题都可以迎刃而解。让我为大家介绍一款强大的数据采集API接口。
|
6月前
|
机器学习/深度学习 数据采集 人工智能
Python系列(1):简洁优雅,功能强大的编程语言
Python系列(1):简洁优雅,功能强大的编程语言
|
6月前
|
Python
python tkinter 最简洁的计算器按钮排列
python tkinter 最简洁的计算器按钮排列
51 0
|
3月前
|
PHP C++ Python
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
63 0
|
4月前
|
前端开发 API 数据库
告别繁琐,拥抱简洁!Python RESTful API 设计实战,让 API 调用如丝般顺滑!
【7月更文挑战第23天】在Python的Flask框架下构建RESTful API,为在线商店管理商品、订单及用户信息。以商品管理为例,设计简洁API端点,如GET `/products`获取商品列表,POST `/products`添加商品,PUT和DELETE则分别用于更新和删除商品。使用SQLAlchemy ORM与SQLite数据库交互,确保数据一致性。实战中还应加入数据验证、错误处理和权限控制,使API既高效又安全,便于前端或其他服务无缝对接。
55 9
|
5月前
|
Python
通过f-string编写简洁高效的Python格式化输出代码
Python 3.6中引入的f-string是Python中最常用的特征之一,它可以让我们编写更干净、更高效和更易于维护的代码,我们今天就由浅入深来详细介绍使用它的一些技巧。
463 4
|
5月前
|
设计模式 程序员 测试技术
老程序员分享:Python数据模型及Pythonic编程
老程序员分享:Python数据模型及Pythonic编程
40 1
|
5月前
|
存储 Python
在Python中,匿名函数(lambda表达式)是一种简洁的创建小型、一次性使用的函数的方式。
【6月更文挑战第24天】Python的匿名函数,即lambda表达式,用于创建一次性的小型函数,常作为高阶函数如`map()`, `filter()`, `reduce()`的参数。lambda表达式以`lambda`开头,后跟参数列表,冒号分隔参数和单行表达式体。例如,`lambda x, y: x + y`定义了一个求和函数。在调用时,它们与普通函数相同。例如,`map(lambda x: x ** 2, [1, 2, 3, 4, 5])`会返回一个列表,其中包含原列表元素的平方。
55 4
|
5月前
|
Python
Python列表推导式是一种简洁的创建新列表的方式,它允许你在一行代码中完成对数据的操作和转换
【6月更文挑战第19天】Python列表推导式是创建新列表的简洁语法,它在一行内处理数据。表达式如`[expr for item in iterable if cond]`,其中`expr`是对元素的操作,`item`来自`iterable`,`if cond`是可选过滤条件。例如,将数字列表平方:`[x**2 for x in numbers]`。嵌套列表推导处理复杂结构,如合并二维数组:`[[a+b for a,b in zip(row1, row2)] for row1, row2 in zip(matrix1, matrix2)]`。简洁但勿过度复杂化。
39 5
|
5月前
|
Serverless 开发者 Python
Python函数式编程:让你的代码更简洁、更高效!
【6月更文挑战第12天】Python函数式编程引入了数学函数概念,强调无副作用和不可变数据。特点包括高阶函数、Lambda表达式、map、filter和reduce。示例展示了如何使用map进行平方运算,filter筛选条件元素,reduce计算元素总和,体现其简洁高效。虽然不适用于所有情况,但函数式编程能提升代码可读性和可维护性。
32 3