小年，假期，春节

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

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

中国环难题和格雷码

最近在翻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。

2009展望

新年将至，想明年开始一个自己的project，目前还没有想好要做什么。用业余时间。继续打乒乓球。继续Blog.继续看书。其他的没想到了。

2008年终总结

2008年即将过去，雪灾，地震，奥运，藏独，经济危机... ... 真是多事之秋，而且很多都和我直接相关，即便不再身上发生，也会强烈的撼动我。所以觉得2008年过得很快，一个悲伤的年份。

今年没有出去玩，和lp一起把旅游经费都捐给灾区了。租的房子也搬了，因为以前的房子卖了。我自己买的房子还没到手，于是又换了一个房子。这个房子房租贵些，但是离上班比较近一些。并且，新房子有网络上，虽然网络质量一开始非常差。于是我又开始玩游戏。到年底房子已经好了，还没开始装修。

今年看了一些书，做了大概几十题的PKU ACM题库的题目。有不少收获，实际做题的帮助还是挺大的，只看不练也不行。但是再做下去也不想做了，因为感觉能做的能做，不能做的还是不太好做。还是多看看书吧。今年买了不少书，不过很多都没时间看，都是马桶上翻翻，上班的间隙翻翻。

工作今年很忙，加入这个组之后。对于linux内核方面有不少收获，不过并不是那么完整。工作其实更多的时间在做很烦人的事情。这两年都没闲下来过。

打乒乓球换了一段时间直板，最后又改回来，现在是oc横版但是不贴满，却发现这样非常好用，解决了我手小捏版问题，哈哈。

2008，没什么可写的了。

让自己快乐起来！

基于染色DFS下的拓扑排序算法

拉屎的时候翻算法导论，无意停在图的DFS，然后到拓扑排序，发现这里的拓扑排序算法是基于DFS的。以前在群里还和讨论过依赖关系的算法，当时我知道的就是那个最简单的不断删除入度0顶点的算法。因为认为DFS(注：普通的DFS）算法可能需要辅助一些特殊的手段来做，不是很方便。
其实删除顶点算法并不是很好用，虽然渐近意义上是o(v+e)，实际使用中和存储结构很相关，而且不好用。然而算法导论上的基于染色的DFS算法很容易做拓扑排序：因为染色使得很容易知道回路，（灰色节点的重入代表回路）。接下来就简单了：

For each v in V do DFS
    If a child is Gray , Fail.
    If v is finished (to be black), insert v onto the font of list L.
return L.

这个算法的复杂度也是o(v+e),但是执行起来效率很高，因为删除顶点的算法需要维护“可删除性”，就是入度的维护。DFS维护一个染色信息，和顶点数相同。但是删除顶点算法可能需要临时的栈/队列来暂存计算出来的入度为0的节点。。
以前老觉得DFS多老生常谈，什么书到那都翻过去，其实发现《导论》上的染色并且维护时间戳的DFS是非常有用的。（记得以前有段时间研究GC遇到过，但是没有在意在别的上面的应用）。看来很多书还要再仔细的多翻翻。

ps，惊闻饭岛爱去世的消息，沉痛悼念！

又到年末

今天是12月13号。。。明天凌晨又是皇马对巴萨，突然又想起四年前的皇马对巴萨，那时只有小罗和齐达内，没有梅西，更没有柏杨。。又是年末，圣诞将至，元旦将至，尾牙将至，春节将至。。。。

到年末就是要写年终总结的，我把07年的总结翻出来，看着觉得好熟悉，觉得近在咫尺，不能想象过了一年了。。今年也是看上去波澜不惊的一年，只是2008年对于身边的环境，的确是一个多事之秋。

准备准备，写一篇总结。。。

买书

又买了一些书，貌似买的太多了。以前还有很多书没看。。。。最近，好像一年半都挺忙的。

《代码之美》

《TAOCP》 第四卷 2 3 4 双语。 （翻译小心的过分了，生涩的很，感觉图词的准确，但是句子有些不通，幸亏是双语的）

《费曼讲物理》 （汗，科普书）。

今年一共买了不少书。前面值得一提的还有

《算法导论》

《什么是数学》 （汗，又是科普。没办法，太菜了，除了看科普，总不能再去学教材）.

《梦断代码》

《编译方面的一些书》 （现代编译原理 现代编译程序设计，重新学习编译原理的东西）

《电影的故事》

换直板了

打了几年横板，换了块直板玩，OC. 觉得横板我一直没找到适合我的打法，握拍的用力和爆发拉球的力经常矛盾。才换的直板，这两天玩了玩，还不错。我发现直板很拉我很容易啊，哈哈。。。另外纠正一个以前的错误，就是拉球的引拍离身体太远，其实应该是先自然下垂，重心先侧倾，这样才能爆发用力。。。以前容易把肩膀架起来..

Linux ARM SWI

这两天终于把那个在Linux下面的SWI搞定了。解决了不少问题。其中一个值得记下的就是一个关于code需要重定位。因为Hook Linux SWI,就需要有段code取代原始Linux的SWI Handler，跳转到自己的Handler然后重新派发,以区分linux系统调用的SWI号和自己的SWI号，自己的就要跳转到自己的Handler，Linux的则要跳转原始的Linux的Handler (vecotor_swi)。这个Handler的代码必须复制到0xC0000000以后的Kernel空间内，不然会有问题（系统死掉，因为handler通过insmod进去，但是模块的函数地址在0xbf000000开始），所以要把code复制到kmalloc的内存里面，同时要小心不能使用一些像LDR的伪指令，需要保证局部跳转不会混淆。其他的问题都是零碎的，也没什么可记录的。 另外遇到一些问题，但是可能和片子有关。

酒量减了

昨天项目组吃饭，其实也没喝多少，我竟然宿醉。在上次和表弟喝酒，也喝了差不多，就没啥。昨天看来喝的太快了！！每次喝都过瘾，喝完就难受，烟戒了，这酒是不是该控制一下了。以前在学校喝酒，下铺给我一个描述：逢酒必喝，逢喝必醉，逢醉必吐。倒。。。
现在酒太多了，回家的时候，老爸也给我酒喝，做无数的菜，我妈也要我喝点，这种温情环境还没喝就有点微醺，所以在家一般喝一点就醉。晕！去亲戚家更是不用说，酒。。。。。


/*********** 华丽分界线 ************/

这个星期比较忙，做了一个比较麻烦的事情，让我不得不回头重新啃ARM汇编。一般的汇编倒也就算了，而这个是非常麻烦的事情：在 Linux 下面自己维护user mode和kernel mode切换，通过ARM的SWI软中断实现（这个名字好多种叫法，一般操作系统书都喜欢说是自陷，这名字好，人和代码一起陷进去。。。）。切换也就罢了，还要下面切回来在切进去，因为要把以前的一些同线程callback已有的代码实现。这汇编写的真是容易晕，栈有上下两个，寄存器也要分模式。终于sample调通了，往项目里插还得花时间。

/***********华丽的分界线**********/

听说最近经济危机找工作的人真的很难找，好多公司也不再招人，招人的都是好几百里面挑几十。