抄抄笔记——格雷码

想起来差不多十年前从图书馆里面一本又一本的借出来各种算法和数据结构的书籍,却从来没读完过...

今天看到一个东西,格雷码。看了半天硬是没怎么看懂(除了第一种递归的办法)...一看到二进制我就懵掉了,脑子里面一点线索都没有的悲催感。想想这块儿的知识应该也会挺有意思的吧?什么二叉树啊,红黑树啊,好像我都完全不了解是怎么个玩法。唉。

抄一点百度百科的笔记。争取过段时间再来看,能多看懂一些...现在脑子里面完全没有一点感觉。

递归生成码表

这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
  1. 1位格雷码有两个码字
  2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0
  3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1[3] 

2位格雷码
3位格雷码
4位格雷码
4位自然二进制码

00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

异或转换

二进制码→格雷码(编码)
此方法从对应的n位二进制码字中直接得到n位格雷码码字,步骤如下:
  1. 对n位二进制的码字,从右到左,以0到n-1编号
  2. 如果二进制码字的第i位和i+1位相同,则对应的格雷码的第i位为0,否则为1(当i+1=n时,二进制码字的第n位被认为是0,即第n-1位不变)[3] 
公式表示

(G:格雷码,B:二进制码)

例如:二进制码0101,为4位数,所以其所转为之格雷码也必为4位数,因此可取转成之二进位码第五位为0,即0 b3 b2 b1 b0。
0 xor 0=0,所以g3=0
0 xor 1=1,所以g2=1
1 xor 0=1,所以g1=1
0 xor 1=1,所以g0=1
因此所转换为之格雷码为0111
格雷码二进制码(解码)
从左边第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值(最左边一位依然不变)。依次异或,直到最低位。依次异或转换后的值(二进制数)就是格雷码转换后二进制码的值。
公式表示

(G:格雷码,B:二进制码)

原码:p[n:0];格雷码:c[n:0](n∈N);编码:c=G(p);解码:p=F(c);
书写时按从左向右标号依次减小,即MSB->LSB,编解码也按此顺序进行
举例:
如果采集器器采到了格雷码:1010
就要将它变为自然二进制:
0 与第四位 1 进行异或结果为 1
上面结果1与第三位0异或结果为 1
上面结果1与第二位1异或结果为 0
上面结果0与第一位0异或结果为 0
因此最终结果为:1100 这就是二进制码即十进制 12
当然人看时只需对照表1一下子就知道是12
...................c[n]=p[n],
解码:

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征,可以递归得到高阶格雷码。由于此方法相对繁琐,使用较少。生成格雷码的步骤如下:
  1. 将卡诺图变量分为两组,变量数目相近(最好相等)
  2. 以逻辑变量高位在左低位在右建立卡诺图
  3. 从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图,依次经过格子的变量取值即为典型格雷码的顺序
三位格雷码(三位格雷码由建立在二位基础上)
AB╲ C
0
1
00
0→
1↓
01
↓2
←3
11
6→
7↓
10
4
←5
格雷码次序:000起点001011010110→111101100终点
四位格雷码
AB╲CD
00
01
11
10
00
0→
1→
3→
2↓
01
↓4
←5
←7
←6
11
12→
13→
15→
14↓
10
8
←9
←11
←10
格雷码次序:0000起点→000100110010011001110101010011001101
111111101010101110011000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除,称为异或乘除,它的特点是无进退位。
如:10101除以11将变成1100余1。
二进制转格雷码
只要异或乘以二分之三,即二进制的1.1,然后忽略小数部分;也可以理解成异或乘以三(即11),再右移一位。
格雷码转二进制
异或除以三分之二,即除以1.1,忽略余数;或者左移一位,再异或除以三,忽略余数。

捡到的诗集

虽然最近一直在三藩活动,但是还是有一些一直想去而没机会去的地方。比如今天终于找到时间和理由来一家历史悠久的书店——City Lights Booksellers and Publishers。听名字就是一个很有感觉的地方,城市光线城市之光。以前留意过一些有趣的活动在这里,就大概估计这会是一个类似于诚品那样的书店,可以坐下来慢慢喝茶看书的。结果,我又以东方思维来推测西方生活了。这就是一个书店,一个纯粹的书店,一个不卖任何饮料的书店。

City Lights (城市之光书店)

City Lights (城市之光书店)

这个书店一进去就是密密麻麻的书架,然后随处可见的标示提醒着浮躁如我的都市人:坐下来,看本书(have a seat + read a book)。于是果断收起手机,随手翻起一本书,寻了一个安静的位置坐下。大概是也没想读一本很厚的诗集,于是随手选了一本薄薄的册子。本也没想读完,却没想到一打开就停不下来,然后竟然就坐在那里翻完了,伴随着心中感慨万千。严格地说,虽然这本书被放在poetry那边,但更像是文化记录的缩影,只是用诗歌这种形式来记录罢了。

IMG_3316

这本书的名字是,I am the Beggar of the World, Landays from contemporary Afghanistan. landay大概相当于歌谣,并不一定是用文字(暂不论语言)记录在纸上,而是以声音的形式进行传播和电子记录(这里还要多谢智能手机的发明,很多语音资料得以被很方便的记录下来)。我不是很了解这个书店的定位,粗粗扫了一眼大致以文学书籍为多,还有很多他们自己出版的。直接的感慨就是美国的文化还是很开放的,至少允许人们出版自己的所见所闻。一句题外话,原来只是感慨有墙的存在所以大家翻墙查阅电子资料不方便,上周一个朋友说其实在国内做人文研究也很苦,因为很多国外出版的书籍都买不到、甚至连图书馆里面也很难借到。这样想想,貌似像我这样随便走进书店然后偶遇一本自己可能感兴趣的书,可能也是一件比较奢侈的事情了。不知道这样的隔阂,到底会造福谁。我们甘愿沉浸于禁锢的思想和快餐娱乐吗?

[......]

Read more


AEA的一点记录

年初的时候连续三天跑到三藩AEA去凑了个热闹。如果这次不是在三藩的话估计我也不会大老远特意跑过去,毕竟这个会都是学术界的人,我跑过去难免有纯粹凑热闹惹人烦之嫌。

首先就是被会议的规模惊呆了。作为一个见惯了国内各种大型会议各种大场面的人,我还是被这样上万人的会议惊呆了。谁说美国地广人稀来着....据某个童鞋说,她从欧洲飞过来入关的时候,SFO的海关都知道了,直接问,“是那个经济学会议对吧?”。这两天的飞机上各种都是来开会的人也不足为奇,据说有好多邻座什么的都是economists或者未来的economists...很多人的直接反馈就是这样的job market确实是很有效率的,是一个高效的matching algorithm,只是不是机器计算的而是大家各种人肉计算出来的。

从上段的描述可以看出来,很多人来AEA就是来找工作的,要么来面试要么面试其他人。像我这种纯粹去围观的估计不多——虽然有很多演讲的sessions但是大家基本也都是各种小圈子里面自娱自乐。说实话,虽然我已经毕业这么久了,但是我也没想到很多session已经到了看标题都看不懂的地步了...哎,分工实在是太细了。

对我来说最重要的估计就是见各种人了——见到了很多快五年没有见过的人。估计不是AEA的话,这些人真的是再过n多年都不一定能见到。有的时候也是感慨,很多在国内的人在国内的时候各种见不到,跑到美国来反而容易见到。各种在美国的人在美国的时候见不到,回国反而能见到。这是一种什么样的给航空公司创造利润的模式...还是用一种最好听的方式来表述吧:大家越来越国际化了。

大牛的话,我主要是去围观Susan Athey的,连听了她两场。一场是比较好玩的bitcoin,都是一些描述性的统计,但是问题本身很好玩,很多新的东西大家都不知道是怎么回事儿,看到一些基本的分析、想想后面的逻辑也是蛮有意思的。另一场是big data,就是她们的tree model去detect heterogeneous treatment effect,这东西前段时间一直在跟,所以到也不陌生,只是感慨很多想法大家其实都有,最后就是看谁有数据谁又坚持下去一点一点把细节都推敲出来。话说中途发消息给某统计学家感慨,人家直接懒懒的回我一句,不记得了。好吧,大牛们的脑路变化都是奇快无比的,不记得就不记得吧。作为一个乖乖的学生,我自己记得学习的心路历程就好了。还去听了Tadelis的两场,虽然很多paper已经听过一遍了,但是去现场玩玩还是挺好玩的,顺便可以见到很多ebay和ex-ebay的人(其中有真人比照片帅的帅哥)。也是一种networking的过程吧。

还有比较好玩的就是不同人的不同状态。很多找工作的人在三天的时间有十几个面试,于是各种亚历山大、繁忙的穿梭在各个酒店之间,偶尔路上碰到也就是匆匆打个招呼。已经进入tenure clock的人相对来讲这次就是来聚一聚的,席间还能听到各种八卦。打算明年上job market的就是提前来看一下情况顺便听听sessions,倒也蛮紧凑的。相比来讲心态最放松的大概就是已经拿到tenure的,来开会更多是纯粹的来开会。各种人的各种状态和各种消息还是蛮有意思的。

还有什么呢?好像已经习惯了每天往返三藩和圣何塞,这样的折腾背后也是预示着什么——既然有那么多事情都是在三藩。


懒散的年末

不知不觉2015年也到了尽头了。想想从14年开始打算搬家,不知不觉的也已经在美国住了一年了。最近进入了一种特别慵懒的节奏,不想去长途旅行,只想安安静静的呆在村里,吃吃逛逛。

年末的休假选择了一种特别的方式——去报了一个英语培训班。大概只是想好好的学一下英语吧。一方面是继续努力的纠正口音,这都是早年上学无知时候欠下的债,只能现在一大把年纪慢慢还。不停的训练口腔里面的肌肉,倒也是蛮好玩的一件事情。另一方面是把快扔给老师的英文语法重新捡起来,什么the怎么用啊,时态怎么用啊,介词怎么用啊…基本上就是各种对于记忆力的训练。说什么语感,其实就是看的多了见的多了,然后自然而然的就这么用了。做了这么一个决定大概也是想了半天之后不知道干什么好。出门开车玩太累,坐飞机又不想制定行程,打开地图画了个圈也没有什么特别想去的地方。最后索性天天往返三番,一边是锻炼自己的意志力,一边也是调整一下状态。人总不能一直懒散下去,有一种紧迫的节奏还是比较舒服的。

想想最近一年,想得最多的大概就是不同的人。试图理解在这边遇到的每个人心里觉得“理所当然”的事情。比较舒服的大概就是大家都是直呼姓名,我是觉得这是一种特别拉近关系的处事方式。观察不同人的心里和行动其实是一件蛮有意思的事情。口是心非的人哪里都会有,所以从文字或者话语中揣测别人的想法就变得很好玩。我好像是把这些当作一种对于异国文化的学习过程了...

大部分时间我觉得美国是一个非常碎片化的社会。美国有很多种族、很多肤色,但是确实很少见不同肤色的聚在一起。美国的社区会被大家标记为白人社区、印度社区、墨西哥人社区、越南社区等等。当然还有中国社区,只是中国社区大致还要分成广东人社区和其他移民社区。我这里完全没有任何贬义——我也有好朋友是从小生长在这里的广东移民后裔。他们完全是另外一个悲惨的故事,一路奋斗上来成家立业,个中辛酸远远不是我们这些跑过来工作读书的可以简单的理解的。 就算在公司,也很少见到不同种族聚集在一起,譬如食物好像就是一道天然的壁垒。自从开始坚果过敏之后,我觉得尊重不同人的饮食习惯真的是对于不同民族的最基本尊重。很久以前一个好朋友跟我说,每个民族的食物都是他们的骄傲,所以无论出门在哪里,多应该去尝试和试图习惯当地的食物,毕竟有那么多当地人是被当地食物养活的。好像不知不觉的我也开始践行这样的尝试。好像在美国,我也没怎么去吃过中餐,除了和中国同事们一起去偶尔开开荤。除了美式煮海鲜和大块烤肉之外,我好像也会偶尔想去吃吃chesse burger,而各种鸡蛋吐司华夫饼的美食早午餐也变成了经常的想念。也会去跟一群同事们吃素食,觉得其实素食还是能做出来不少花样的。唯一需要检讨的大概就是我做饭的时间真的是屈指可数。好像越来越不愿意花费时间在厨房,不知道是不是一种挺悲哀的事情。嘴越来越刁,厨艺越来越差。

这一年我在试图让自己的生活变得更加简单一些。以前很多事情就算不喜欢也只是默默的忍受着,现在则是要么果断的说不,要么付诸行动远离。好像耐性是有点越来越差了?或者说是对于越来越多的事情变的越来越不在乎,而会越来越在乎那少数关键的事情。反正有得必有失,所以如果只是得到更多而不失去什么,那好像不是很公平呢。很多伤心的事情大概就是想想就过去了吧,人总要往前看,move on。这是一种成熟还是冷血?

好像,有这么一个安静的周末,懒懒的睡起来,然后找个人来人往的咖啡馆,点个精致的甜品,静静坐着,打开电脑,写点东西,记录一下,偶尔发发呆。这种人群中的安静还是挺让人享受的。加州还是一个相对热情和平静的地方,人们还会多少谈一下梦想。舒缓的音乐配上点餐的喧闹,也是挺有一种市井之中生活的味道。我不知道是不是只有los gatos可以这样休闲。希望这样的生活应该是一直可望而且可及下去的吧。

2015.12.19 于 Fleur de Cocoa, Los Gatos.

Fleur de Cocoa, Los Gatos

Fleur de Cocoa, Los Gatos


Sunsets in a year

有的时候可以静静的在那里用镜头捕捉日落,也是一种奢侈的享受。可以作为一个衡量生活质量的因素。

数数今年还是有幸看了几场日落。日出基本上是爬不起来了。

  • 加州,三藩。在酒店顶层的爵士吧里面一边听着演出,一边喝着鸡尾酒,一边出神的看着落日。
  • 加州, Big Sur。落日时分开车开到big sur海边,在临海丛林中略略穿梭,边走边拍边笑逐颜开。
  • 以色列,特拉维夫Jeffa古城。日落之前,跑到古城码头边居高临海的餐厅,临窗落座,边品中东美食边看落日西下。
  • 以色列,Galilee湖。慢慢的绕着湖开着车,开呀开,开呀开。左边是夕阳西下渐埋山中,右边是初月新生照耀湖水。
  • 上海。已经不记得在上海的高层餐厅看过多少次落日了...M1nt属于浦西绝赞,东西不错而且安静,而浦东则首推丽思卡尔顿,虽然柏悦也是个不错的选择...

有的时候觉得生活已经惬意至此,我还有什么不满足的呢?有多少自由可以如斯挥霍。