落园

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

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

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

递归生成码表

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1. 1位格雷码有两个码字
2. (n+1)位格雷码中的前2ⁿ个码字等于n位格雷码的码字，按顺序书写，加前缀0
3. (n+1)位格雷码中的后2ⁿ个码字等于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起点→001→011→010→110→111→101→100终点

四位格雷码

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起点→0001→0011→0010→0110→0111→0101→0100→1100→1101→

1111→1110→1010→1011→1001→1000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除，称为异或乘除，它的特点是无进退位。

如：10101除以11将变成1100余1。

二进制转格雷码：

只要异或乘以二分之三，即二进制的1.1，然后忽略小数部分；也可以理解成异或乘以三（即11），再右移一位。

格雷码转二进制：

异或除以三分之二，即除以1.1，忽略余数；或者左移一位，再异或除以三，忽略余数。

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

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

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