二进制的二三事

二进制是计算机的自然语言,逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此,二进制中的0和1往往也是我们解决实际问题的利器。

阅读全文>>

二进制是计算机的自然语言,逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此,二进制中的0和1往往也是我们解决实际问题的利器。

Task1:求一个固定长度集合所有子集

最直观的方法就是穷举:对集合中的每个元素来说它要么在当前子集中,要么不在当前子集中,以此依次类推穷举出所有可能的值。如果我们用0表示该元素在当前子集中,用1表示该元素不在当前子集中,我们就可以用一串0/1序列来表示当前的子集。

例如集合{a, b, c, d, e}中的子集{a, b, c}可以用“11100”来表示,子集{c, d, e}可以用“00111”来表示,空子集{}可以用“00000”来表示。

那么对任意固定长度的集合a[n],我们可以从a[0]开始穷举a[0]在子集中和a[0]不在子集中两种情况,再依次类推从a[1]开始一直穷举到a[n-1]为止。于是我们可以得到一个很直观的递归程序:

void sub_sets_recu(int index, int length, char *array, char *bits)
{
	int j = 0;

	if (index >= length) {
		for (j = 0; j < length; j++) {
			if (bits[j] == '1') {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
	else {
		bits[index] = '1';
		sub_sets_recu(index+1, length, array, bits);
		bits[index] = '0';
		sub_sets_recu(index+1, length, array, bits);
	}
}

但是递归版本的缺点就是需要一个额外的数组bits来存储0/1序列,那么有没有办法改进呢?我们可以先试试把递归改成迭代的方式会不会有效果。

迭代的关键就在于明白你究竟要做哪些计算步骤,为此我们可以先画出递归函数的Execution Tree来看看:

—                       ○
|                     0/  \1
|                     ○    ○
|                  0/  \1   .
|                  ○    ○     .
n层             .       .      .
|                .         .
|               .           .
|             /  \        /  \
|           ○   ○     ○    ○

上图中,第i层的值为1的边来表示a[i]在子集中,值为0的边表示a[i]不在子集中,那么从根节点到所有叶子节点所经过的边的组合就是所有可能的子集组合,例如从根节点到最左叶子节点的组合为“00000”,即空子集。根据完全二叉树的性质,第n层有2^n个节点,所以共有2^n个不同的子集。既然所有的解都已经存储在这颗二叉树中,那么我们自然就可以依此构建一个遍历所有路径的迭代算法。

思路是有了,但是实际编码中我们需要用到一个跟二进制编码相关的trick了。我们知道任意一个十进制的数是可以用二进制来表示的,反过来我们也可以用十进制来表示二进制啊,“用二进制来思考”其实就是这个trick的关键。既然我们的解是“00000”~“11111”,那么它们自然可以用十进制的0~31来表示。很自然的我们就可以想到如果我们依次遍历0~31这些数,根据它们二进制值中每一位的值是0还是1即可确定当前元素是否在子集中。关于二进制的位操作等相关知识Matrix67的blog[1]有一个系列写的很不错,在此就不再赘述。

void sub_sets_iter(int length, char *array)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < (1<<length); i++) {
		for (j = 0; j < length; j++) {
			if ((i & (1<<j)) != 0) {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
}

再加上测试用的main函数:

int main()
{
	char a[5] = {'a','b','c','d','e'};
	char b[5];
	int i;

#ifdef USE_RECU
	for (i = 0; i < 10000000; i++) {
		sub_sets_recu(0, 5, a, b);
	}
#else
	for (i = 0; i < 10000000; i++) {
		sub_sets_iter(5, a);
	}
#endif
	return 0;
}

好,代码全写完了,当然应该比试比试两个算法孰优孰劣。测试平台是:cygwin + gcc 3.4.4 + Core2 Duo T7300@2.0GHz

在测试时已经把两个算法中的printf给注释掉了,只比拼速度。先把gcc的优化设成-O0看看:

$ time ./recu.exe

real    0m8.847s
user    0m8.811s
sys     0m0.046s

$ time ./iter.exe

real    0m5.093s
user    0m4.999s
sys     0m0.046s

再看看gcc -O3的结果:

$ time ./recu_o3.exe

real    0m8.285s
user    0m8.234s
sys     0m0.031s

$ time ./iter_o3.exe

real    0m1.887s
user    0m1.796s
sys     0m0.031s

结果显示迭代算法优于递归算法。感兴趣的朋友可以反汇编一下编译器优化后的代码,看看为什么迭代算法优化后能快那么多。关于递归与迭代已经有很多分析了,简单说来递归更加直观易懂,但是栈的开销比较大;迭代的算法不容易一开始就想出来,但是一般来说效率更高。从编译器的角度来讲,部分的编译器能把相对简单的递归算法转化成迭代算法,因为递归的算法对编译器来说是更友好的算法,更易于在此基础上做更多的优化。从体系结构的角度来讲,递归算法更易于发挥CPU流水线的特点让多步运算同时执行,而某些特定的架构,例如GPU就没有对递归提供有效的硬件支持,因为栈空间是一个大问题。

Task2:小白鼠试毒药问题

实验室里有1000个一模一样的瓶子,但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话,会在一个星期的时候死去,其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药?

这个问题关键是跳出思维,并不是说瓶子和小白鼠必须一一对应,然后我们用1000只小白鼠,每只各试一瓶药水,等一个礼拜然后出结果。其实我们仔细想想,小白鼠试毒只有两种结果,非“死”即“生”,又是一个0/1状态。很显然我们可以再次构建一个0/1组成的二叉树,由此即可表示不同的试毒结果。假设我们需要n个小白鼠,那么2^n-1应大于等于1000(因为有1000种可能的结果,减一是指要除去小白鼠全部不死的情况 — 多谢danqi指正),那么最小的n就是10了。

总结

解决此类问题的关键在于找到能用0/1表示的状态,然后想办法用0/1组成的二进制数来表示不同的结果,从而达到节省存储空间,提高解题效率的目的。

二进制真是神奇,文章的最后附一张0和1构成的Fibonacci数列(来自[2]):

相关文献

[1] 位运算讲解系列文章
[2] Fibonacci数列转二进制图形的惊异发现

转载请注明来自www.parallellabs.com

瑞典Ericsson总部Master Thesis面试回忆录

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。[…]

阅读全文>>

前言:去年4月份我申请过一些6月份开始的毕业设计和暑假实习,最终拿到了Ericsson的master thesis offer和另一个哥德堡小公司的summer intern,Volvo在我拿到summer intern后也给了interview。现在应该已经有不少一年级的同学要开始找暑假实习了,我觉得你们可以考虑申请6月份开始的毕设(等毕设结束后再回学校把剩下的课程修完)。下面是我去位于Kista的Ericsson总部面试的经历,希望对大家有用。Summer Intern总体上来讲难度比thesis大很多,因为很多瑞典人也要竞争这种职位,而且那些提供summer intern的小公司也不太喜欢招foreigner。

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。

发信人是后来面试我的Dr. V.,我一查竟然是UCxx的出身,心想又是UCxx啊!不禁由衷的仰慕,立刻对之后的Interview十分的向往。事后证明Dr. V.人真的非常的nice,虽然有些许龅牙,但是至少英语听起来比较舒服啊!

之后的信件往来就是确定面试时间之类,定下下下周五之后立刻跟身在Kista的yoan师兄联系商量借住事宜(在此对师兄的热情相助表示深深感谢!是你让我在Kista感受到家的温暖啊!还顺带连累你熬了个通宵 囧),然后就是买往返的火车票之类。一切定好后剩下的两个礼拜就开始拼命准备,囫囵吞枣扫了些论文,再跟着看了些英文面试的资料,甚至还去了Career Office做了一次咨询。

这其中发生了一件比较逗的事情。因为哥德堡到斯德的来回火车票加起来600多SEK,我心想这一趟下去怎么的也得1000块了,要不问问看他们能不能给报销?再加上外国公司以往报销路费的事听了不少,我就借着发信问问题的机会顺带来了句:“I am wondering whether you will undertake my travel fee for this interview?” 猜猜人家怎么回的?

“it’s not possible to 报销路费, so我们只能电话Interview了”,我心想,大哥我这菜鸟要电话面试不就相当于直接管你要据信么,再说我票都定了大不了当去旅游好了,于是连忙给他发信解释说没关系云云。

2009 May 14th

早上6点的火车去Stockholm,4点半起的,等5点的第一班tram去Central Station。顺利等到4路电车,心想时间肯定来得及,耽误不了。但是不幸恰恰在心情放松麻痹大意的情况下发生了。我在离火车站还有两站路的时候突发奇想拿出口语书开始模拟英语面试,自己边模拟面试官边想着怎么回答,简直就是左右互搏,天人合一,不亦乐乎,十分忘我。练了5,6分钟后我发现不对了:怎么窗外还能看见火车啊?我仔细一看,我靠!还真是Central Station的火车,其中就有我要坐的x2000!我心中大叫不好,刚刚停的那站就是火车站,我给错过了!!我赶紧收拾东西站在门口准备在下站下车赶紧再坐回去,结果老天真给我开了个大玩笑:过了上一站之后Tram就进入郊区了,开了至少5分钟才到下一站!那5分钟简直就是我人生最漫长的一段时间之一,脑子100%运转,不停看表计算时间,同时储备体力随时准备狂奔。

5分钟后终于到达下一站了,赶紧下车,到对面站台看反方向的车几点到:5分钟以后!这意味着我到火车站后离发车只剩10分钟不到!!!而且我还从来没去过火车站都不知道火车在哪!天无绝人之路,我发现旁边竟然还有一个车站!赶紧对了下时间,Tram7马上就到,又多出了5分钟!老天保佑,我心急如焚的等着不紧不慢的7路小电车,来了!上车!走!到!门开的一霎那,我真是卯足了劲往站台冲啊!事后回想我大概只用了1分钟不到就找到了X2000的站台。这还多亏瑞典的火车站不像国内的那么大,还要进候车厅再排队检票上下楼梯什么的,站台离车站正门也就2-3分钟的路,而且上车后再检票。我悬着的心终于放下来了,事后回想就算当天没赶上我也可以再买下一班的,大不了先上车后补票,还好是我之前订的就是周四走周五面试。虽然我这不叫大难不死,但也算是必有后福啊!

顺利到达Stockholm。斯京的火车站和地铁站是连在一起的,下火车后直接就去地铁售票处买了张24h的通票(100SEK),直奔Kista。话说这个Kista号称瑞典最大的科技园区,里面不仅有Ericsson全球总部,华为瑞典分舵等众多IT公司,KTH也有一个分校区在那边。出了Kista地铁站直接就是一个大型Shopping Mall,在把正补觉的师兄吵醒之后顺利放下行李。中午吃了师兄做的红烧肉拌面,话说那个红烧肉确实很够味,真是赞!

下午就出去Kista园区去寻我明天面试的地点去了。来了Kista我最大的感受就是,整个Kista到处都是Ericsson的人。不管是在Shopping Mall里的Restaurant还是在工业园区的大街上,到处都是挂着蓝色Ericsson牌子的人,简直就是Ericsson大山寨。后来听到一个说法,Ericsson这样的国民企业其实更应该被看做一个Community,在Kista的shopping mall里面甚至有专门的Ericsson员工价,由此可见一般。顺便说一句,上次回国刚下飞机在机场大巴上,坐我旁边的竟然是个瑞典小哥,仔细一聊竟然也是学CS的,从Stockholm来中国找他中国女朋友,于是我就问“你是不是给Ericsson工作”,结果竟然猜对了。由此可见爱立信有多庞大。

事实也确实如此。一开始我找到的最显眼的是一栋白色的大型Ericsson办公楼,整个楼占了一个广场的大小,气势直逼瑞典皇宫了(当然更现代点),真不愧是世界级大公司的全球总部啊。于是我就去reception问我的面试官是不是在这栋楼办公,结果人家告诉我:“不好意思,你找的人在对面那栋楼办公,出门后直走就到了”。等我出去仔细一看,原来Ericsson Research是另一栋大红楼。我猜可能那栋大白楼里面应该都是Ericsson负责工业产品的部门吧。踩点完毕后就回家继续做准备去了。Tips:对面试要提前踩点,特别是去不熟悉的地方更要多做准备,因为瑞典人很忌讳迟到(瑞典交通发达,地铁非常准时,也没什么堵车,所以没有迟到的理由)。

虽然最后我拿到了这个Offer,但是说实话在面试之前我还是非常紧张的。这可是我第一次英文面试,两个面试官都是顶尖大学的PHD,还顶着Ericsson总部的光环。我做的主要准备如下:

1)根据Position Description看了几篇该领域的综述型Paper,以到达快速入门的目的;

2)仔细研究该Position的Requirement,结合自己的CV自己进行了若干次模拟面试

3)准备了自己本科毕设的资料(一页A4插图,直观明了)和,因为这个跟该Thesis有点相关

4)给面试专门准备了一份CV,突出了自己项目经验跟该position的相关性

面试的流程大致如下:

跟两份面试官打过招呼后直接把CV和Transcript递上(省了人家自己打印的功夫,而且给你第一印象就是你准备的很充分。“我把简历都给你带过来了,上面的都是你们需要的”)。Dr.V.人非常好的先给我介绍了一下该Thesis的大致背景,很好的帮助我消除了紧张情绪并帮助我快速进入状态。在了解到项目的大致框架后我适时的接过话题(适时把握话题的主动性,不是被人牵着鼻子走。“我对这个很熟,请听听我的想法”),抛出了我对这个项目的具体实现的想法(虽然有些当时我的想法有些许错误,但是很好的表现出自己对这个项目的兴趣,就像是说:“你看,我自己脑子里已经有一个实现了,我很有可能能把这个项目完成的很好”)。

再聊了一些项目的话题后面试官就开始问我的简历上的项目经验了。我就一个一个跟他们解释(“我做过的东西跟这个Thesis都很相关,我很有竞争力”),其中有几个他们比较熟悉的项目他们就会问你一些技术问题或者算法问题。不过只要自己对项目的背景知识和本身的实现比较熟悉基本没什么问题,而且就算真的不会直接说不会也没关系。我其中就有2个问题直接说了不会,很可能他们因为看重我其他的背景和我的学习能力所以没影响我拿offer。

我感觉我整个面试过程中最出彩的地方在介绍我的本科毕设部分。回想当年在白混了3年之后,心想最后一个毕设怎么的也得拿个A做出点像样的东西来,要不大学白过了,于是狠命搞了半年终于如愿以偿。正好毕设跟这个Thesis很相关,当我拿出我做的prototype的照片并向他们介绍它的功能的时候,我分明的感觉到两位Ericsson Researcher都被我打动了(“给我Offer吧!本科毕设我都拿A了,你们这个Thesis我肯定不会让你们失望的!”)。

最后Dr. V.非常Nice的送我下楼,我在电梯里又跟他聊起不能报销差旅费的事情,最后我对他说了我生平最有打动人的效果的一句英语:“I just want to let you know my serious and positive attitude for this position.”结果Dr.V.非常配合的笑着对我说:“Yes!You have!”

The End:May 19th下午正准备跟妞妞mixi,突然接到一个010开头的电话,我还奇怪难道是北京打来的?后来才知道在瑞典Stockholm的区号也是010。也许大家都猜到了,其实就是另一位面试官打来的Offer电话。

P.S. 虽然因为种种原因没去Ericsson,但是我仍然深深的被Ericsson HQ的魅力所吸引,它向我展现了一个世界电信巨头的风采。而Stockholm,它的美丽更是让我留恋。希望下一次妞妞能跟我再一次同游斯德。

P.S.S. 猜猜Kista最大的中国人群体里在哪?不错,就是华为!华为真是牛逼,我问过好几个瑞典人了,华为真的是一个爱立信强有力对手的存在,直接把分舵开到Ericsson老家,有点新东方把分舵开始ETS总部的意思。在此祝华为越来越牛逼!早日出台Kista华为员工价!