我要发芽

代码发芽网重新支持临时代码

半瓶墨水 — Thu, 12 Nov 2009 09:56:39 +0800

(上上周做的了，直到今天才有时间写）

代码发芽网改版以后，把临时高亮代码的支持去掉了，也就是说，不管你有没有登录，所有的代码都会发布，别人也看得到

当时考虑的情况是：保不保存都没关系，因为用来高亮的代码都是要贴到网上的，给出了“高亮不保存”按钮反而添乱。

然后有朋友在贴了代码以后，写信给我要求删除；如是者三，我也纳闷，跟其中一位朋友聊聊为啥，才知道有时候贴代码是在本地用的，并不想公开。

想了又想，决定还是尊重用户的选择；为了区分，我加上了一个“临时自用，请不要保存”的选项。

一道老面试题 - 为什么镜子可以颠倒左右却不能颠倒上下？

半瓶墨水 — Wed, 11 Nov 2009 08:32:36 +0800

题目描述如下：

题酷发芽网#155：想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒上下？

这道题目其实有很大的迷惑性，面试官是在考察你的逻辑思维能力

有两种答案如下：
1. 因为人的眼睛是左右对称的，而不是上下对称得（这个是有问题的，闭上一只眼，还是同样的结果）
2. 因为镜子里面人的左右是反的，上下是正的（等于把题目重复了一遍）

事实上我也想不到一个很好的回答，只把一条条的想法列在下面，欢迎讨论

镜子里的影像的“左右”，如果相对于站在镜子前的人来说，根本没有变化，左还是左，右还是右。所以所谓颠倒的左右，是指镜子里的人的左右跟现实中的人的左右相反
只要镜子放置的位置，能够对于某个参考坐标系“取反”就会产生“颠倒”的效果
所以我觉得是参照物的不同，上下的参照物是地心，左右的参照物是人的中心
对于站在镜子前的情况，地心并未被取反（因为地心跟镜子在同一个平面上）。题目还是有限制的“你在镜子前”，否则如果你站在镜子上，或者把镜子顶在头上，镜子就能颠倒上下
实际上，严格来说，只要镜子稍微偏离一点点，使得地心跟镜子不在同一平面，镜子就能颠倒上下，站在镜子上和头顶着镜子只是一个人能够清楚感受这一点的特例
但是由于“左旋”跟“右旋”始终是镜像关系，所以左右始终是能颠倒的，不论怎么摆放

网站图标在线生成工具 - Ever the best online favicon creator(Beta)

半瓶墨水 — Fri, 16 Oct 2009 08:28:41 +0800

最近几天搞装修，七拼八凑买到了一个不到五十平的蜗居，暂时先用着吧
等老子有钱了，哼哼…买它两个五十平的，一个留着住，一个拆着玩儿

资金不足的情况下，只能够自己张罗装修得大部分，一个字：忙！

所以这个工具写好一周了，直到今天才有时间把它介绍给大家

下面请我们以隆重的掌声欢迎这份给祖国大妈六十周年庆典的献礼。。。啪啦啪啦
（路人甲：这也能献礼，这不是欺负人家不能拒绝嘛。。。）

这是一个工具
这是一个制作图标的工具
这是一个制作网站图标favicon的工具
这是一个专门制作网站图标favicon的免费在线工具

好吧，废话不多说，关门，放图片：

列一下这个网站图标(favicon)在线工具的功能：

1. 支持铅笔、刷子、直线、方框、填充、魔棒填充（不大容易介绍，自己研究一下就行了）等工具
2. 可以移动整个图片，还有方便的吸管工具
3. 随时可以清除重来，还可以无限回退所有改动操作
4. 支持透明色（就是背后是那种棋格图案的地方）
5. 支持所有主流浏览器：IE/Firefox/Chrome/Safari

实际上，由于功能实在太过于简单，直接去试试就行了，只要记得工具栏最右边的图标是保存并下载就行

后续开发计划
准备这一个月有时间的话，看一下flash和AS3，用它来实现一些图片处理的功能

后续的功能主要有：

1. 从图片导入图标：上除图片或者打开web图片，图片放缩成16×16，然后开始
2. 从已有的网站图标开始创作：输入网址，导入其favicon
3. 生成的图标可以在线共享，在发芽网上永久保留
4. 从已有的图片导入调色板
5. 更大更好更全：支持创建32×32的icon，支持渐变色，支持创建光标文件(.cur)，支持创建动态光标。。。

我很清楚，这些计划里面的大多数都会泡汤，兴趣的转移总是很快的

还没有失去兴趣之前，能做多少做多少吧

实现细节
好了，王婆自夸结束，说一下实现细节：
1. 前端就不说了，就是js+css
2. 后端使用python做的一个array to ico的工具，代码共享在代码发芽网上了，有兴趣的自己去看看

关于浏览器的不兼容，前面已经抱怨过了，这次忍不住又出来抱怨一下：

先说说IE: 速度慢，贼慢，现在还没有时间调performance，不知道到底是啥原因。
另外，它支持设置css的background-position属性，但是不支持获取这个属性。
要想获取的时候，必须先要得到background-position-x，再得到background-position-y，然后组合起来。。。

相关讨论参见：Fix for background-position in IE

再说说Firefox: 速度适中，但是不能直接设置和获取background-position-x/y。
写多了web页面的人都知道css sprite是怎么回事吧，不能用直接设置、获取-x/y，意味着你先要获取background-position，然后通过字符串解析出x和y，然后改变其中一个值，再组合起来设置回去。。。

相关讨论参见：Background-position-y, firefox-fails!

最后说说Chrome: 速度飞快，流畅的就像本地程序一样，支持background-position，也支持单独的-x/y。似乎一切都很完美。

但是当我把鼠标光标变成自定义光标(cursor属性)的时候，比如油漆桶工具，鼠标就得用个油漆桶样式的，鼠标的焦点(hotspot)就在油漆桶下面的尖尖上，但是这个hotspot的设置在chrome下是没有用的，它会固执的认为(0,0)才是真正的hotspot！

而且，不同于前面说的IE和Firefox的bug，没有办法可以绕过。

对于方框和划线工具来说，这是很不爽的-鼠标点击了的某个格子，实际却作用在了左上角的格子上…
无奈之下，只好写了一段代码判断浏览器，对于Chrome进行特殊处理，用系统的cursor来代替。。。

简单的应用，居然引出这么多的浏览器bug，说明准守w3c css3的标准是多么重要啊…日！

在题库发芽网上试用了Google Ajax Search API

半瓶墨水 — Mon, 14 Sep 2009 08:25:09 +0800

题酷发芽网在每个题目页面的右侧边栏底端都可以看到相关题目，这是最近对Google Ajax Search API的一次尝试。

插播一条广告：

欢迎订阅题酷发芽网的两个RSS：最新题目 & 最新回答

关于Google Ajax Search API，不多说，自己看链接里面的内容，或者简单理解为：让你的网站都可以拥有Google那样快的搜索速度！

当然，前提是：Google索引了你网站的内容，而且是最新的，这个好办，做个sitemap就行了，有了这个，Googlebot抓的很勤劳的，Django自带了一个sitemap组件，很好用

另外，在题库发芽网的首页上，你可以看到右上方有个小小的搜索框，在里面输入“球”然后回车，你就来到了题酷搜索结果页面里面，上面啥也没有，但是在右侧边栏最下面，你可以看到许多结果。

你还可以试试在那个Google搜索框里输入想搜索的内容，呵呵实时相应的哦。

另外：如果你在题库发芽网上发过帖子的话，可能会注意到那里也有Ajax应用 - 比如你可以输入“二叉树”，然后按Tab把焦点挪到内容输入框，就会出现已经存在的相关问题列表，主要用来防止重复发文。

这个也是仿Stackoverflow的功能，Stackoverflow针对的是英文内容，只要mysql端支持full text search就可以做到，但是对于中文内容来说，还需要分词以及mysql中文匹配插件，做起来很费劲，就暂时用Google Ajax API替代了。

最后，关门，放代码：

JavaScript语言: 打算用在题库发芽网中的：基于Google API搜索同类内容

/*
*  How to load jQuery and then use the Search API with it.
*/
 google.load("jquery", "1");
 // on page load complete, fire off a jQuery json-p query
 // against Google web search
 function OnLoad(){
   var url = "http://ajax.googleapis.com/ajax/services/search/web?q=华容道游戏%20site:fayaa.com/code/view/&v=1.0&rsz=large&callback=?";
   $.getJSON(url, function (data) {
     if (data.responseData.results &&
         data.responseData.results.length > 0) {
       var results = data.responseData.results;
       var html = "";
       for (var i=0; i<results.length;i++) {
         var r = results[i];
         html += '<a href="' + r.url + '" title="' + r.content.replace(/(<([^>]+)>)/ig,"") + '">' + r.title + "</a><br/>";
       }
       $('#content').html(html);
     }
   });
 }
 google.setOnLoadCallback(OnLoad);

面试题之链表问题汇总 - 倒转单链表 / 有环链表 / 倒数第k元素 / …

半瓶墨水 — Fri, 11 Sep 2009 08:50:25 +0800

现在插播一条广告：

欢迎订阅题酷发芽网的两个RSS：最新题目 & 最新回答

关于链表问题的面试题目如下：

面试题之链表问题 - 倒转单链表

 找出倒数第k个元素(或中间元素）

二级链表展开

 链表加法运算

 删除环状单链表的一个节点

 两个有序链表的合并

 如何判断两个链表是否交叉

 判断单链表是否有环？

求两个有序链表的交集

最新结果参见：题酷发芽网上标签为“链表”的题目

牛b的比特流

半瓶墨水 — Thu, 10 Sep 2009 08:49:18 +0800

你知道下面这段代码干了啥吗？

a ^= b b ^= a a ^= b

如果你碰巧知道，那么 x^-x 呢？WTF~!

冯.诺依曼计算机中，程序无论编成什么样子，最终都会变成一堆堆的0和1，也是因为这样，对于bit操作的研究，一直都没有停歇，已知的很多优秀的算法实现，都用到了bit操作

一般的语言，比如python或者C(++)都支持 与& 或| 异或^ 反~ 操作。这四种基本操作的意义这里就不说了(关于完备性，参见离散数学)，通常我们还会用到 << 以及 >> 操作，分别表示把bits向左、右移位。另外，所有加减乘除的操作，内部同样是bit搞来搞去。

你可能见过这种代码： a>>=1 ，这个是干嘛的，仔细想想就明白了，这是除二操作，比直接除法运算要高效一些，同理，乘以2就是a<<=1

或许你还见过这个：(UINT)-1 ，这是啥？翻开计算机基础教材看看补码那一节就知道了。这是win32编程常用的小手段，代表0xFFFFFFFF

还有异或操作，这个操作自己就可以组合出其他所有逻辑操作！因为他是完备的。它还有一个非常非常有趣的性质：a^a = 0 ！

回到文章开头的内容，那三行a和b异或来去的代码干了什么？

a ^= b //a=a^b, b=b b ^= a //a=a^b, b=(a^b)^b=a a ^= b //a=(a^b)^a=b, b=a

到最后一行，可以看到，这三行代码完成了a和b的交换(swap)。有些公司面试的时候会问：知道怎么不用中间变量实现swap(a,b)吗？ok，你会了！恭喜你，学会抢答了！面试官脸色一变，随即抛出另一道题目：

有一组数字，从1到n，中间少了一个数，顺序也被打乱，放在一个n-1的数组里，设计算法在O(n)时间O(1)空间内找出丢失的数字！

怎么办？
还好你学会了异或运算：ok，很简单，从1到n异或一遍，再从从数组里面异或一遍，最后的值就是那个丢失的数字

面试官脸色再变，说数字丢失了两个，咋办？没想清楚的看这里。

插播一条广告：

欢迎订阅题酷发芽网的两个RSS：最新题目 & 最新回答

好了，异或运算先说到这里就先打住，说说 x & -x 这个变态的数字吧，他是啥意思？你仔细演算了一遍发现，哦，原来是一个数字最后面那个1，比如x=b111111100，x & -x 就是b100 (这里的b表示binary，二进制)

这有啥用？这时候下一个面试官进来了，再次抛出一道题目：找寻下一个“二进制1等量”数：

对于两个二进制数，如果他们的二进制表示中1的数目相等，我们称他们为“二进制1等量”的
给定一个数，设计一个算法F找出比它稍大的“二进制1等量”数
（稍大的意思是离它最近的那个）
比如：
3 = 0011 5 = 0101 F(3) = 5
6 = 0110 F(5) = 6 ...

这可咋办？别急，通常面试官放出这种题目来，是看你有没有思路，别被题目吓住就行。
不过，我最终被答案吓住了，以下是求解的算法：

 unsigned snoob(unsigned x) {
   unsigned smallest, ripple, ones;
   // x = xxx0 1111 0000
   smallest = x & -x; // 0000 0001 0000
   ripple = x + smallest; // xxx1 0000 0000
   ones = x ^ ripple; // 0001 1111 0000
   ones = (ones >> 2)/smallest; // 0000 0000 0111
   return ripple | ones; // xxx1 0000 0111
 }

感觉如何？反正我看到里面的二进制搞来搞去已经傻掉了。整个求解过程可以参见这里，里面的分析相当精彩，不容错过。

说到这里，比特流，不再只是流水的那个流，已经是“迎风一刀流”这样的流了

真别说，有个叫Henry S. Warren的家伙就专门研究了bit操作，还写了本书，叫做Hacker’s Delight(翻译版叫做《高效程序的奥秘》)，其中第3章（点击下载英文pdf）就详细而又完备的讲解了bit流，值得一看。上面那个找寻二进制“1”等价的问题在文章里有详细描述，他甚至指出了这个问题的现实意义 - 比如从N个数里面挑选K个，你可以从K个1开始，一直生成到K个1加上(N-K)个0为止，由于算法效率高，不需要递归，用起还是很爽的！（参照阅读递归方式的X-Selection算法）

该书中还提到：

x & (x-1) 可以用来确定一个数是不是2的幂
x & (x+1) 可以判断一个数是不是2^n-1这种形式，也就是说，全都是1!
x | (x-1) 可以把x后面的所有0变成1，00101000 => 00101111
((x | (x-1)) + 1) & x 可以把最右边那一串1给抹了，01011000 => 01000000
x | (x+1) 可以把最右边的那个0变成1，10100111 => 10101111
…

等等等等，还有很多，好了，就此打住，想了解更多的自己看可以免费可以下载到的pdf样章

Update：有趣的是，发文24小时之内就读到一位朋友在Google Reader上面分享的文章：bithacks.h - bit hacks header file，里面定义了一堆的宏来做位操作：

B8(x) - turns x written in binary into decimal,
B_EVEN(x) - tests if x is even (bithack #1),
B_ODD(x) - tests if x is odd (!(bithack #1)),
B_IS_SET(x, n) - tests if n-th bit is set in x (bithack #2),
B_SET(x, n) - sets n-th bit in x (bithack #3),
B_UNSET(x, n) - unsets n-th bit in x (bithack #4),
B_TOGGLE(x, n) - toggles n-th bit in x (bithack #5),
B_TURNOFF_1(x) - turns off the right-most 1-bit in x (bithack #6),
B_ISOLATE_1(x) - isolates the right-most 1-bit in x (bithack #7),
B_PROPAGATE_1(x) - propagates the right-most 1-bit in x (bithack #8),
B_ISOLATE_0(x) - isolates the right-most 0-bit in x (bithack #9),
B_TURNON_0(x) - turn on the right-most 0-bit in x (bithack #10).

我也把代码转贴了一下： Bit Hacks Header File(bithacks.h) 和 Bit Hacks Test Cases(bithacks_test.cpp)

好了，想继续研究的，附赠两个Link：
http://graphics.stanford.edu/~seander/bithacks.html
http://www.cs.bris.ac.uk/Teaching/Resources/COMS21102/slides-dan/

呵呵文到最后，说两个关于自己的：

1.
我的18位身份证号码，1和0占据了14个！

2.
写这篇文章翻出两年前的旧文：中文和英文哪个表达能力更强？二进制和十进制哪个更厉害？

这篇文章是我2007年的得意之作，至今依然是，可惜很少有人感兴趣，特此自我推荐。

Python语言: head.py 输出文件开头的8个字节的二进制表示

半瓶墨水 — Wed, 09 Sep 2009 15:15:18 +0800

最近在写一个在线favicon编辑器，其ico格式很让人不爽，写了个工具生成ico格式的文件
为了手动检查生成结果，写了这个脚本检查其文件头内容：

Python语言: head.py 输出文件开头的8个字节的二进制表示

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# Recently I start to write an ico file maker
#   this script helps on analyze the file header
#
# Usage:
#   head xxx.ico    - output 16 bytes
#   head xxx.ico 32 - output 32 bytes
#
importsys
f=open(sys.argv[1],"rb")
L=16
iflen(sys.argv) >=3:
L=int(sys.argv[2])
bytes=f.read(L)
foriinrange(0,len(bytes),8):
printbytes[i:i+8]
 xbytes = ["%02x" % ord(b) for b in bytes]
 print
 for i in range(0, len(bytes), 8):
   print "x " + " ".join(xbytes[i:i+8])
 def to_bits(b):
   bs = []
   while b:
     bs.append(b&1)
     b>>=1
   bs = map(str, bs)
   bs.reverse()
   return "".join(bs).zfill(8)
 bits = [to_bits(ord(b)) for b in bytes]
 print
 for i in range(0, len(bytes), 8):
   print "b " + " ".join(bits[i:i+8])

题酷发芽网发布 - 精彩、经典IT面试题库、智力题库收集

半瓶墨水 — Thu, 03 Sep 2009 09:29:21 +0800

挖哈哈，终于超过100个题啦！

题酷发芽网上线试用了一周以后，现在正式发布了！

有啥用？多了去了：比如面试前回顾，比如面试人的时候拿抽几道题，又比如刚学了一门新语言想练练手。。。

一些经典面试题如下：

微软经典面试题：

面试题之链表问题 - 判断单链表是否有环？
面试题 - 字符串两边对齐
 传说中的微软面试题 - 飞机加油问题
 聪明的囚犯抓豆子问题
 面试题之链表问题 - 判断单链表是否有环？
面试题之链表问题 - 找出倒数第k个元素(或中间元素）
面试题 - 字符串两边对齐
 面试题 - 原地倒转字符串
 面试题 - 寻找丢失的数字

Google经典面试题：

100*100部分有序矩阵数组的排序
 25匹赛马血拼Top五
 整数0-n中"1"的个数

更多面试题、经典编程算法题参见：题酷发芽网所有题目

BTW: 界面基本参照StackOverflow.com，SO太让人敬仰了

更新发芽网到Django1.1，因为傻逼年年有，今年特别多

半瓶墨水 — Sun, 09 Aug 2009 15:09:16 +0800

今天忍不住把发芽网后台更新了到了Django1.1，不是因为这个更快更好，主要是因为有个傻逼，天天到代码发芽网上孜孜不倦的贴黄色网站链接，删帖删到手软

代码发芽网搞代码高亮的网站，留垃圾留言之前看看坑行不行？

最最关键的是，这些标明了是“Sex Movie”以及“Adult Video”的链接，都他妈是不可访问的！！！
是可忍孰不可忍！挂掉他！！！

这时候才发现，在Django原来自带的后台里，删除内容的时候只能一个个点开，一个个删

这才想起来最近Django更新过，去碰碰运气看到了1.1版的后台已经支持批量删除了，说不定大家都被这样的傻逼惹毛了

直接备份数据库，然后更新，批量删除

另外又检查了一下，还有一堆内容不长过10个字符的帖子，都是匿名帖。

日，没办法，空间有限，挥霍不起，在匿名发帖的时候加上了Captcha

匿名发帖的朋友，对不住了，麻烦发帖前做一下简单的算术：个位数的加法，应该还行吧
实在觉得烦，注册并登陆一下就不用填了，5分钟不到的时间，一年都不用重新登录
如果不想注册又不想做算术又想要贴黄站链接，请直接来信交流，谢谢

BTW1: 科技进步原来真是由色情推动的
BTW2: 4500个帖子里面有600个spam，真是无语了

代码发芽网高亮引擎更新了(版本：1.1dev_20090523)

半瓶墨水 — Sat, 23 May 2009 15:08:21 +0800

终于有时间把代码发芽网的高亮引擎Pygments到1.1dev_20090523版
支持的语言多了不少（已经支持164种编程语言了，包括asp.net），效果还不错

其他的更新包括：
. Firefox下右边滚动条时隐时现引起页面跳动的问题
. 编辑代码界面的改进（更高的编辑框等等）
. 添加了收藏按钮
（就是页面右边靠着顶栏的那个长长的小按钮，来自addthis.com），以前用十八帮的，不知为何会引起页面混乱
. 修正了在Chrome浏览器下“代码评论打分按钮”布局混乱的问题

新添加的编程语言支持
==================
* Antlr/Ragel, thanks to Ana Nelson
* (Ba)sh shell
* Erlang shell
* GLSL
* Prolog
* Evoque
* Modelica
* Rebol
* MXML
* Cython
* ABAP
* ASP.net (VB/C#)
* Vala

还包括一些bug fix，详见Pygments的Changelog