Google彻底被封的提前上演

昨天晚上和今天google和其相关服务抽风。原因不明。 大量网友开始悼念google，不过貌似今天晚上部分恢复。 真的，我的确很愤怒，这几天cctv和相关喉舌霉体小丑的表演真的让人作呕。也许Google被封在即，今天只是提前预演。 悲凉，给google设计一个logo。

据四川质量报2006年4月10日报道：“成都很多窗户封闭的空调车上都没有救生锤，一旦遇到紧急情况（如突然发生火灾），势必将造成悲剧和极大的损失！”接读者打来的热线电话后，记者全面调查——— 【点题】： 2006年3月1日下午1点左右，一辆由四川射洪开往深圳龙岗的客车在南（宁）梧（州）高速广西横县六景镇甘棠河大桥横县方向100米处突发大火，车上42名乘客（含3名小孩）除17人成功逃生外，烧伤8人，死亡16人。“要是当时有足够的救生锤，就不会有那么多无辜的生命葬身火海！”一位幸存者回忆说。 如此重大的安全事故，再次为我们敲响了警钟。长途客车如此，市内公交车又是怎样的呢？ 近日，记者调查了成都市38路、61路、34路、62路、27路、56路等线路的20余辆空调车，发现这些车窗封闭的空调公交车上，乘务员大多不知道什么是救生锤，而且大部分空调公交车的“救生锤”都只剩下了一个空架子，上面悬挂的救生锤早已不知去向。

沉默日

不久的将来，这个日子不再成为敏感的日子。可是大家依然“维护”网站。显示一个“今日维护”的界面， 成为一个纪念日。如同那个关闭电灯的日子一样。

买了4个轮子的...车....两辆

山地车，捷安特最便宜的 上班用。 和LP一人一辆。

穿墙上Blogger

Fuck GFW!!!!!!!!!!!!!! 真是穿墙骂了隔壁的。真郁闷。把blogspot和blogger一起封掉了。 马上2^6了，看来敏感期要来了。封吧，封死你们这些老王八蛋。

公平，公正。不是公关！

看到网络上很多关于70码的评论，有一个争论的点，就是仇富。这真是很奇怪的一件事情。我觉得大部分网友并不是仇富，而是仇不平。因为在中国，几乎可以想象的就是接下来的公关以及背后的操作。因为什么，屁股不干净啊。不但不干净，还不敢脱下裤子。ZF公关这本身就是一个悲凉的事情。

公平，公正。不是公关！

需要反思一下自己

越是忙的时候，越容易陷入“自己到底在做什么”的疑问之中。的确，和很多朋友一样，对很多充满抱怨，对所做的事情感到烦躁，乏味。然而却又非常的忙碌，把大好的时光浪费在很多无意义的事情上。可是却无可奈何。

我也没办法那么潇洒，随便就放弃眼前的生活，换一个城市，换个环境又开始。26了，开始步入中年，总不是只为自己生活。可是我真的失去了目标，茫然不知所措。我甚至买了基础科的教材，开始补课。可是下班后又感觉很累而无法继续看书。曾经说，不图什么这个那个，要的是快乐。随心随性。可是现实就是现实。现在所能做的，只有一边像机器一样运作，一边使劲查找自己的目标。每天上午打开机器，可是过一会，看看右下角，竟然是下午了。

我曾经的理想是做一名程序员，为此努力了很多年，走了很多弯路。的确，做一个真正的程序员，是很难的。曾经也猜测，Coding应该是个工具，功夫在之外。现在发现这个猜测基本是正确的。只是很难逃脱coding时堆砌一些东西所带来的快感。

我应该反思自己，我是否应该准备去应对突破自己的挑战。可是如何去做呢，到底什么是目标呢，快乐吗？

富家子飙车撞死人

杭州警方通报富家子飙车撞死人案
网友人肉搜索
其他
关注此事，看看黑暗中的手

想买个单反

最近看上了宾得的KM，入门玩玩。真羡慕那些有钱人，入门就杀D80...

ARM Linux的一些片段（一）

因为工作原因，对这个部分有接触。平时看代码和一些文档的细节感觉过段时间就忘记了。所以要做个记录。可能其中还有错误。吧一个对人很有启发的记录下来。不过这些内容很零散，平时也是需要才看。以下说的arm是支持mmu的arm9以上.

Linux支持三级页表，作为其默认的页表结构。ARM是两极页表。PGD和PTE。从pgtable.h里面可以可以看出一个work around的实现。PGD和PTE并不是直接对应ARM硬件的页表目录项。而是做了一些为了linux上层的要求的一个方案。首先，他把4096个pgd项变成2048个，物理上还是一个pgd指向一个256个pte项的数组的，这没办法改。但是pgd指针逻辑上合并成一个，各自指向的的pte数组也合并。并且是连续的。

   pgd             pte
 57  * |        |
 58  * +--------+ +0
 59  * |        |-----> +------------+ +0
 60  * +- - - - + +4    |  h/w pt 0  |
 61  * |        |-----> +------------+ +1024
 62  * +--------+ +8    |  h/w pt 1  |
 63  * |        |       +------------+ +2048
 64  * +- - - - +       | Linux pt 0 |
 65  * |        |       +------------+ +3072
 66  * +--------+       | Linux pt 1 |
 67  * |        |       +------------+ +4096

以上内容摘自Linux ARM pgtable.h, GPL.

这512个pte项合并起来，这个pte分配的页（一般linux需要一个pte表在一个页里，代码注释也写了）还剩下一半的内容，刚好可以存放arm不支持的一些标记（Linux pt 0, 1)，而这些标记是linux必须的，比如dirty。这个方案还非常具有可扩展性，不依赖arm本身的标记。dirty标记的实现是通过对arm支持的权限fault的中断来写这个标记。这样方式是相当于一种模拟。

对于不同cpu版本，set_pte的实现是用宏##拼的函数，这些函数不再arch/arm/kernel而是arch/arm/mm里面,找个v6的实现里面可以看到实现：(这段代码上面的一段注释不知道是不是写错了， ptep - pointer to level 2 translation table entry (hardware version is stored at -1024 bytes)，明明是2048个字节，代码也是，也许是我理解错）
这里就看到先偏移2048个字节找到“真的”pte做事。

ENTRY(cpu_v6_set_pte)
154         str     r1, [r0], #-2048                @ linux version
155 
156         bic     r2, r1, #0x000003f0
157         bic     r2, r2, #0x00000003
158         orr     r2, r2, #PTE_EXT_AP0 | 2
...
            tst     r1, #L_PTE_PRESENT
176         moveq   r2, #0
177 
178         str     r2, [r0]
179         mcr     p15, 0, r0, c7, c10, 1 @ flush_pte
180         mov     pc, lr

关于ARM的模式，arm本来有7个模式，而linux只有两个user和kernel。于是Linux的实现就把包括中断处理模式页转到同一个模式下做事，就是arm的所谓超级用户（svc）模式，实现这个的办法就是改写备份寄存器spsr为svc的模式，然后movs pc到svc模式，然后再调用处理函数，这样除了用户模式其他的模式执行环境都是同一个模式了。
感觉选择svc模式作为kernel也是很自然的，swi一看就是用来做系统调用的，直接进入svc模式。
这段代码是在宏里面，然后根据不同模式进行展开在头部。

.macro  vector_stub, name, mode, correction=0
885         .align  5
886 
887 vector_\name:
888         .if \correction
889         sub     lr, lr, #\correction
890         .endif
891 
892         @
893         @ Save r0, lr_ (parent PC) and spsr_
894         @ (parent CPSR)
895         @
896         stmia   sp, {r0, lr}            @ save r0, lr
897         mrs     lr, spsr
898         str     lr, [sp, #8]            @ save spsr
899 
900         @
901         @ Prepare for SVC32 mode.  IRQs remain disabled.
902         @
903         mrs     r0, cpsr
904         eor     r0, r0, #(\mode ^ SVC_MODE)
905         msr     spsr_cxsf, r0
906 
907         @
908         @ the branch table must immediately follow this code
909         @
910         and     lr, lr, #0x0f
911         mov     r0, sp
912         ldr     lr, [pc, lr, lsl #2]
913         movs    pc, lr                  @ branch to handler in SVC mode
914         .endm

另外,对于不支持高向量的arm，因为中断向量表从0开始，所以需要把第一页保留，不作为用户空间。

排列生成

继续读TAOCP笔记，上次就准备写，一直没写。上次到格雷码再往后就没看了，看了非2进制格雷码。然后就来看排列生成。平时没时间看，只有厕所的时候翻一下。

排列生成给的第一个基本算法是一个老算法，但是看上去却不是那么明显的一个算法。初始化的a[1] <= a[2] <=... <= a[n]，然后生成所有按字典序的排列。

  while(1)
  {
1   VISIT(a);

2   j = n - 1; 
    while(a[j] >= a[j+1] && j > 0)
      j--;
    if(j == 0)return;

3   l = n;
    if(a[j] >= a[l])
      l --;
    swap(a[l], a[j]);

4   k = j + 1; l = n;
    while(k < l)
    {
      swap(a[k], a[l]);
      k ++; 
      l --;
    }
  }

这算法看上去一点都不明显，除掉外面的大循环，里面就是每次按照当前的a得到下一个字典序的a。 书上解释了这个算法的几个大步和历史。不过这个笔记记录我当时另外的一个方式来理解。从一个比较蠢的算法开始，得到本质上一致的解释。 一个明显简单的算法是：

per(a, i)
{
  if(i > N)
  {
    VISIT(a);
    return;
  }
  a[i] = 0;
  while(1)
  {
    a[i] = alloc(a[i]);
    if(a[i] == -1)
    {
      return;
    }  
    per(a, i + 1);
    free(a[i]);     
  }
}  

这是个递归的算法，相当简单，从排列最原始的想法开始，递增的填一个数，然后拼接剩下的数的排列，。这里填数需要一个类似分配的方法，所以叫做alloc,就是当前过程中还没用上的数,并且大于传入的参数以获得递增的去拿这些数。alloc的实现可以非常蠢，比如，标记所有已经用过的，然后从头走到尾，得到一个没用过的并且大于参数的结果。

第一个算法从第一个排列开始，第二个算法在第一次回朔之前也会到达这个状态，OK,第一个排列成功产生。 对于算法过程中任何一次回朔，第二个算法的执行的规律是：free掉这个数，回到上一次，这时候free掉的数将会被分配器回收，然而，如果上次尝试去alloc下一个数的时候，必须刚才free的比他目前所用的大，否则，他还得乖乖的free他的数，再回到上一次，一直进行下去。这是显然的。于是，第一个算法的第2步得到解释：获取一个能增长的a[j]，他的条件很简单：a[j] < a[j + 1].

我们找到了a[j],我们要从那个愚蠢的分配器中alloc一个新的数，在上次的回朔中，除了找到a[j]，还得到一个结果,a[j + 1] >= a[j + 2] >= ... >= a[n].有序的。这些数都被free而回收在分配器中，那么a[j]去调用alloc的结果就是从这一批数中得到那个最小的但是比a[j]大的数，所以第一个算法的第3步得到解释。a[l]就是alloc的结果。

这时候，第2个算法又要继续增加递归的深度了，很显然，a[j]增长了，接下来a[j + 1]...a[n]将从分配器中alloc到新的结果,显然，他们会是从小到大的顺序被分配，第一个算法的第4步讲得到这个分配到下次回朔之前的结果，也就是得到下一个排列的结果。那么排序就是了，不过这时候不需要冒泡也不需要快排，因为刚刚free的a[j]和a[l]交换之前是有序的：并且：

  a[l + 1] < a[l] < a[l - 1] 
  a[l + 1] < a[j] < a[l]         a[l]需要是比a[j]大的最小的数
所以
  a[l + 1] < a[j] < a[j - 1]

这意味着交换后这个本来是单调降序的依然保持着这个降序。这样重新排序为升序就是不断交换前后，老大变老末，老2变老末2。

这样，一个蠢算法就是相当于行动上证明了一个好算法。

这是谣言

最近听说合肥ZF内部有开会说15-20号可能有5.5级以上DZ发生，目前只通知GWY之类的内部职员，做好准备。对LBX不公布。安全起见，删除内容若干。

一定是个谣言。但是我要记下来。

谣言止于智者，我不是智者，在中国，我们都是瞎子。
谣言始于智者，我不是智者，在中国，我们都是傻子。
谣言！！

2009年4月6日晚地震

 
今天凌晨1点半，收到表弟的短信说晚上可能余震，他一切都好，他们小区的人都跑出来了，问我怎么样。我当时迷糊了，难道地震了？原来10点的时候肥东发生3.5级地震，合肥都有明显感觉。。。囧！我一点都没感觉到。

方言，优越感与普通话

上海人为了上海话动肝火，以前就猜到如果将来如果有对方言与普通话的激烈斗争，肯定是在上海，广东这些发达地区产生“大声音”。汉族的方言种类估计是没法计算的，因为很多地方不到几里路就是完全不一样的方言（我老家就是）。方言除了表达之外，还给了各色人贴上标签，典型的中国地域标签。本来方言和普通话的问题是不存在的，那些多语言的国家tmd语法不一样，也可以交流。如果我们保护方言，那就不要丢弃他，去研究他，搜集他。如果跨地域交流有问题，大家都学普通话。这里根本不矛盾。只要我们不去不允许说方言。普通话又可以给我们跨地域交流。挺好的事儿。

问题就是那些优越感一族非要死磕着他们觉得具有优越感的方言。拒绝普通话，还打着保护方言的幌子。其实他们内心瞧不起别的方言，不屑说普通话，因为只有那个方言才能体现他的优越感而已。

卸载金山词霸

金山词霸彻底被我废了，根据TR的推荐，选择灵格斯。
容易崩溃，启动的时候老是死在IE载入上，让人心烦。你出广告也不要影响我正常使用啊。
总是用IE打开链接，从来不尊重的浏览器选择。

说道词典软件，我就想起我上学时候写的单词猎手，一个简单的词典软件，当时想法还挺好的呢。也是开放词库，txt格式的词典。不过那个时候根本没有那么多热心的人来做词典。在csdn上只见下载不见有人联系我说增加词库。不过词典的编译是运行时开始的，启动速度成问题。后来换用硬盘持久的的索引和词库，不过那个设计我后来觉得有问题。就干掉了。另外有版权问题，有点怕。只敢从网上拼凑一个6级不到的词库。囧！

SGI被收购

SGI终于结束了。sigh, OpenGL.

不能用Blogger自带的编辑器

这玩意自动插的br会和pre在iE6下发生奇特的BUg. 算了，以后还是全手工来吧。

线程上下文友好的RPC

最近工作需要，把系统重新构造为多个processes。以前的api调用有部分转换为RPC。因此需要做一个RPC的模块原型。RPC的基本实现一般操作系统上都有介绍，最简单的模型是（基于Message的同步RPC)

Client:                           
...                              
rpc_call(){                     
   send(api_id, args);          
   recv(ret);
   return ret; 
}

Server:
                          
while(...) {
   recv(api_id, args)
   ret = call(api_id, args);
   send(ret);
}

如果server只有一个线程，那么所有的RPC call都是同步的。一般不会这么简单的去使用，于是Server会创建线程来来处理，可能是为每个调用，也可能为每个连接。这也是目前看到一些流行RPC的做法，也是KISS的做法。可是，当你不是去做新东西的，而是为了改造以前的东西的时候，这些KISS的就不能方便的直接用了。 稍微复杂一点，双向的RPC调用的处理。普通函数调用经常也会有callback的情况。也就是说双方都会成为Server。如果对方发送callback的RPC调用到当前调用者，如何处理会比较好。简单的应用上面的模型，callback会在调用者进程某个处理RPC的线程内处理。如果在这个Callback内部又要调用到对方，也就是出现乒乓球一般的你来我往，那么每次跨越进程都会有新的线程产生。这的确不太好，而且还有一个问题，就是普通函数经常会有同步callback，而且这个callback的线程环境需要是和caller相同的环境。当有这样的假设时候，用户就可能在一些递归的锁上出问题，比如递归的Mutex.以前OK的code因为线程环境的更换而死锁。（不过，的确用户不应该做这样假设。） 新的简单的做法就是，调用者在发出调用请求后，并不是等待结果，而是进入和server类似的行为，就是和对方做回和，在调用者线程内处理对方的call。

Client:
...                              
rpc_call() { 
   send(api_id, args);

   while(...) {
      recv(msg);
      switch msg type:
          case ret: return ret;
          case call: call api from msg   
   }
   return ret;                       
}

在这里，server的RPC处理函数call内部可以rpc_call回到Client，产生互相的递归调用。同时借用的双方本地堆栈。（一开始我用SystemV的share memory和semaphore，就需要自己维护这个堆栈，稍微麻烦一点，里面的socket操作send和recv都需要用semaphore取代。不过感觉share memory的stack不安全，最后还是放弃了而是使用简单的socket，扩展更好，只是需要一些数据的拷贝开销）。这样，以前同步callback的代码专程RPC之后，线程上下文将保持一至，并且少了重新连接和新建线程的开销。 以上只是示意的伪代码，实际实现还需要不少要考虑的东西。不过我对这个找到这个简单的解法感到满意。程序员不是总是遇到可以随意发挥的时候，面对曾经的那些泥潭，憋屈的时候也能找到coding的乐趣。

一个悖论，两个我

有想过一个奇特的问题，就是记忆的复制，好像以前也想过，写下来吧。

假设我们的大脑，或者说我们的意识活动是某个层次上的粒子的活动表现。粒子并不是说一定是某个物理上的概念。比如，如果你的意识是一段程序，那么你的粒子是0和1的组合，定义这个层次是为了一个”可复制“性。这段程序，很显然是可以复制0和1的方式到另外的机器上，独立运行。我们也一定能在这个层次上复制相同的状态过来。也就是说，出现了两个意识，两个我。这两个意识开始同时演绎，将会得到什么呢？

我睡着,冻结意识，复制一份，然后醒过来，”我“将是谁？如果这是成功的，我出现在任何一个新的”我“上都是无法解释的。找一个第三观察者，可以定义真的源头的”我“，和复制出来的”我“。两个”我“醒来后，将对新的”刺激“生成记忆和动作。那么，一开始的论述，相对源头的”我“，将不复存在。就是有多个”我“，世界出现了多个。世界是相对我的，不是绝对的。我看到了另一个”我“，和当前相对我的世界。我的记忆中还有睡着之前的记忆，甚至可以知道我是”真我“，这不重要，重要的是，不是复制了”我“， 而是复制了一个"世界"。


或者，我们的意识不能这样的”确定“和”复制“的， 他是随机的，或者无法冻结,无论如何，无法细分到一个层次定义出可复制的意识。哪怕我们有分子复制，或原子复制机之类的东西。"我"就是独一无二的？

我是个很无趣的人

最近身边很多人在学车，还有很多人也在搞装修，，前段时间还有很多人在炒股，为什么我对这些一点兴趣都没有呢。貌似除了吃喝，真的没有什么 共同的东西了。我真是个很无趣的人。

“背”算法和写代码

高中的时候第一次接触快排的时候，发现即便知道了算法的思想和基本过程，自己写出一个完整的代码，并不是容易的事情。不像做上学题目一样，基本思路有了，基本也就做出来了。当时真的很沮丧，发现写出一个一定程度上可以证明是正确的，都是很难的。当时发现不仅仅是快排，很多程序都不是那么好写，或者说只能写出个样子，却无法放心这样写是不是对的，包括后来的著名的2分查找。当时我就有个疑问，难道学编程，这些基本的东西要背下来么？不会的，不会的。

再后来的日子里，一直伴随着这种失落感，编程接触的也越来越多。有些很容易写出代码，比如动态规划的程序，或者逻辑非常清晰的程序，比如大部分递归的算法。有些很麻烦，基本上要写的时候还要debug，比如一些复杂的数据结构的操作代码，但是这些还算容易从代码上证明基本上正确。最难写的，还是上面提到的某些“短”的代码，比如二分查找和快排之类，如果不知道里面的变量在循环等结构里保持何种关系，所谓循环不变式，只有每次写的时候，从书上认真再去复查，才敢心安。

于是后来开始思考，我要依赖代码重用还是依赖书籍，甚至自己背下来？重用也许是最合理的想法，所以不要再去造轮子。不过，总有一些情况你无法重用曾经的代码，使用一些标准库，然而在很多语言，标准库对于基础算法的封装，并不总是够用的。（Knuth对传统黑箱式的重用就说"有偏见"）。另外，从某个意义上，不会造基本的轮子的程序员估计在很多人眼里算不上合格的程序员。 其实大部分情况下都是复制粘贴吧，也许。本质上还是依赖书籍。不过，即便如此，不理解为什么代码这么写，复制粘贴不能解决心中的问题！于是乎，还得把代码的一些关键的地方“背”下来，记下隐藏在i，j后的循环不变式，可能发生的边界问题等等。去年做acm题目的时候，发现大量的时间还是费在一些基本算法的使用上，后来才知道，真正参赛的选手都是要把那些基本算法背的很熟才行的。不过，如何写好算法的代码本身也是个值得思考的问题。一个代码写的好不好，缩进和命名都是表面的，关键是，是不是很尽量能被理解和证明正确性。可读性并不仅仅是文本上的。现实中，我们可能经常看到一些代码，看上去也是工作的，有些复杂，然而，很难看到其中一种条理性：这一段之后，会是什么样的，这个循环每次的入口是个什么样的，我能控制得了。失控的代码，结果总是等到debug的时候修修补补。其实是和自己过不去，代码基本上没办法证明是对的。

我平时写代码还算认真，也喜欢仔细思考每一小段代码的前后（广义上，都算入口和出口）是不是可控的。但是项目一忙，而且很多事情本身就是一个比较让人烦闷的事情，比如merge code，人总是来不及思考，结果让更多的时间给了将来去浪费。

PS，后来，终于在算法导论上看到了快排的一个更优良的划分方式，这个比以前的霍尔的快排要容易理解和证明的多，当时感到十分惊艳，也觉得终于拿掉了当年心中的一个石头。这个算法，好“背”多了。

无论如何，做一个心中合格的程序员还是很难得，还有很长的路。很多人看不起Coder,可是，做一个合格的coder, 也许比很多角色要难很多！而做一个合格的coder，也许是很多所谓光鲜角色的基础，然后，现在看上去很多都是本末倒置。

一个字

黨

来源

可恶的Blog css，装修

有段时间没更新了，其实我每天都在更新这个可恶的Blog的Html模板。我本来css就不懂，烦死了，好不容易搞了一个满意的，在IE6下面显示有问题，而且问题还都不一样.最后只好还是选择这个最初用的，稍微改改，不敢再改了。

======分界线===============================

装修开始了，目前顺利。我负责验收，LP负责买东西。

======分界线================================

尝到一次扩展性的甜头

最近几天工作比较忙，却尝到一次扩展性的甜头。就是去年的一块我当时经过思想斗争，留下一个扩展的可能。并且在当时没用上的地方粗略的填了代码，整体也一直维护着这个扩展性。其实我一直很烦莫名其妙没有需求的过度扩展，所以当时心理还有点打鼓。后来仔细分析觉得还是有必要。结果这几天发现这个扩展非常有用，如果要加这个新的需求，可能重构很多地方并且有大的梳理。所以比较顺利。

设计的时候，能考虑到哪些是需要扩展的，那些是过度的设计是很难的，一方面是设计人员的经验，另外现在软件经常受到需求不明确的干扰。需求似乎一直是变化的。虽然重构等手法能拥抱这种变化，但是简洁不应该成为设计不作为的借口，那就是过度的简洁。至少在设计的时候，能预料到不明确的地方，即便不实现，如果将来有重构的可能，重构的成本也应该在设计时候考虑进去，而不是一句：没事，到时候再重构。

我为什么写Blog

貌似每个写Blog的人都有经常问自己为什么写Blog.如网上这篇我为什么要Blog。以前我也经常问自己写blog干嘛。回头看看历史，竟然5年了。2004年开始写Blog，那时候有一个小圈子，现在这个小圈子还在，只是我不再使用Blog和这个圈子交流了。从2006年左右搬到Blogger，或者说Blogspot， 就基本上很少去公开现在的这个Blog,除非和人交流时候互相交换。如今这个Blog的读者是非常少的，目前我知道的只有两个，哈哈。也就是说，2006年之后，我的Blog就是相当于主要只是写给自己看了。

中国环难题和格雷码（二）

继续笔记，上次提到的格雷码的一个迭代规则，在实际编程中，这个算法在计算后置0的时候带有一个循环，因此效率并非最好。TAOCP上提到计算后置0的算法是可以不循环的，这个在TAOCP的前册有提到，不过我没有。但是有一本书，《Hacker's Delight》，上面应该有。不过这些算法可能依赖机器字长，书上提到一个通用的算法，速度很快。
算法的本质和上次提到的一样，快得原因是是找到k的进位不需要循环，而是维护一个长度一致的数组f,其中f[i]表示:

1 如果找到一个块 a[j + 1] = 0, a[j] = a[j - 1] ... = a[i] = 1, a[i - 1] = 0. 那么a[i] = j + 1
2 否则 f[i] = i;

显然，对于一个原始码的一次进位，那个进位的位置就是f[0]指向的位置。(f[-1] = 0)
算法每次都拿f[0]的位置，确定需要修改的g(k)中的变化的位，上次说过了，这个进位的位置和格雷码的变化位是对应的。另j = f[0]，进位发生后, 需要修改一些f，保持f的含义:

         j
         |
         v
..011..11011...11
         |
..011..11100...00

首先f[0] = 0，然后上面可以看出刚刚取出的变化的j,则

f[j] = f[j + 1]       /*这是为了把f[j + 1]指向的块向右扩展一个，因为当前的块变成了 f[j + 1] ~ j */ 
f[j + 1] = j + 1      /*把以前的f[j + 1]清为指向j,规则2*/

书上说这个算法是“眼花缭乱”的快。而且这种算法是很有启发性的，他的意义不仅仅在于这个问题上面，通用性可能应用到其他类似的地方。

过年归来

初五来到合肥，又要开始枯燥的上班生活了。

年过得很开心，虽然现在年味是很淡了。还了了一个大事情，就是父母和LP的父母见面，之前和LP都很害怕，不知道会不会尴尬，结果他们4个人一见如故，相谈甚欢。我的恋爱之路终于步过新的里程碑了。

在家看到五舅，小舅的小孩已经长很大了，还有表姐的小孩也长大了。



=== 华丽分界线 ================================

回家看了些电影，把一直没完整看的教父1 和 2都补全了。另外看了大烟枪等喜剧，然后看了悲情城市，不少人觉得悲情城市里面有亲日和悲伤的结局，但是我觉得这是一部充满希望和美好的电影，政治的苦难只是背景，并不是表现的主题，主题还是台湾的人，无论是日统，国统，228，族人相残这些政治之难之后，他们仍然吸收和保有自己的文化，孕育自己的家庭。所以看完挺感动的，这才是一种真正的坚强。如果只有悲伤，怎么会有最后的一家吃饭的长镜头，几个小孩已经长大，香火不断，坚强不息。

小年，假期，春节

今年农历年挺早的，下个周一是我农历生日了--小年。灶神在古人的书中是个帅哥啊。“男不拜月，女不祭灶”，为啥，灶王爷帅啊。昨天去买了车票准备回家，结果以前常坐的那次车停运了，这次得很晚才能回到家。。。离家不过两个小时的火车，真晕，铁路就是霸王啊。上面通知了，要配合几个老美，估计得在假期要几天来加班。本来今年经济危机，假期比以往的长，结果发现不但加班，连付费加班都没了。不过经济危机就是这样，台湾那边好多同事还有很多在国外出差，而且是过年期间。

去年回家之前是雪灾，今年看来没有这个担心了吧。经济上的雪灾，至少不能阻断回家之路，父母，家庭，才是温暖的所在啊。祝天下所有父母新年快乐，身体健康，家庭幸福。虽然现在的社会年味越来越淡，要不就是商家为了赚钱营造的那些浮华的气氛。但是一年的辛苦之后，我们总要有个休息。推杯换盏之间，热气腾腾的饭菜，让我们忘记那些不如意的事情，尽情的爱身边的人。

中国环难题和格雷码

最近在翻TAOCP的第四卷第2册。看到格雷码问题的一个产生方式是与一个叫做中国环问题相关（作为中国人，我竟然不知道这个东西）。而这个问题我去年在做ACM题目的时候，刚好也有个类似的题目，关于一个囚犯解脱的问题规则和这个一模一样。当时我仅仅得到结论就是每一个步骤只能做一种动作，因为任何动作都是自反的，就是再做就回到上一步了。那么问题就是如何选择第一步，选完第一步，后面的计算是确定的。我当时的程序列出那些数据，那时候并不太明白格雷码的相关知识，也就作罢了。因为需要一个公式才能做那个题，否则就需要硬迭代，范围太大了。
那个格雷码的公式就是格雷码与他的索引之间的关系。就是TAOCP的g(k)与k的公式，是一个总结的结论然后用数学归纳法证明的。

g(k) = (b[n], b[n - 1], ... b[1])
k = (a[n], a[n - 1], ... a[1])
则对 j <= n 有 b[j] = a[j] XOR a[j + 1] 

这个公式就能解释这个中国环问题为什么是格雷码问题，不过高大爷写的过程的不太直接。其实就是找出k ++的格雷码增加的规律。
当 a[1] = 0的时候， k + 1不产生进位，则g(k)的最后一位取反(1 XOR a[2] =NOT(0 XOR a[2])
当 a[1] = 1的时候， k + 1产生一个传递的进位，另（假设n无范围） a[j + 1] = 0, a[j] = a[j - 1] = ... = a[1] = 1有

 X011...11                    Y10...00
+        1     
----------  k   对应 g(k)   ------------
 X100...00                    Z10...00

可以看出，这个进位使得g(k)的0最右0不变，并且第一个1不变，然后紧接这个1的位取反，Z = 1 XOR X = NOT(0 XOR X) = NOT(Y)
这样两个g(k)的变化规律刚好就是中国环的取环和下环规则:
1 最右一个环可随时取下和放上
2 可以取下或放上一个环，这个环的右边的环是放上的，右边的右边到最右边的环都是取下的。
再回到刚才的情况a[1] = 0 或者1的判断其实就是一个简单奇偶判断。
那么一个k可以求出g(k)，反过来g(k)求k就是 （利用第一个公式联j到n + 1位得到的式子,然后XOR这些式子消去中间的式子,这种推导在书上是不会写的，连一个习题都不算）

 
a[j] = b[j] XOR b[j + 1] ... XOR b[n]

上面这个公式对于编程的时候，是可以简单的动态规划的，就是求得a[j] = b[j] XOR a[j + 1],a[n] = b[n]. 于是当面对一个环的状态时，可以转换到对应的自然数索引k，根据k的奇偶这样就可以确定该如何往下走了。 PS,我看得这个书是双语版的，翻译有一些不妥的地方，坚定了我在豆瓣建了一个翻译勘误小组，因为有些翻译还是很容易误导别人的。还有上面的[]索引有些地方看上去超出了范围，其实本没有范围，对于自然数，超出就是0。