首先为什么要做这样的判断呢？当你要strcpy活着strcmp或者hash一个字符串的时候，传统的方法是每个byte进行比较。以strcpy为例，当一个字符串比较长，我们用32（或者64位）的字长进行copy的话，一次拷贝会拷贝4个byte，能节省很多时间（忽略内存对齐等情况）。但是，使用32位的字长进行拷贝一个难点就是判断字符串的结尾，因为字符串长度不一定是4的整数倍，每次从内存中取4个byte，我们需要判断这4个byte中是否有某个byte是0，从而判断字符串是否结束。最传统的做法就是对每个字节进行一次判断，或者将所有字节乘起来，看结果是否是0：http://www.spongeliu.com/unsignedchar*p=(unsignedchar*)&v;bool hasNoZeroByte=*p&&*(p+1)&&*(p+2)&&*(p+3);上面的代码需要12步操作，并且需要若干乘指令，效率不高。一种传统有效的方法是通过对每个byte进行一次掩码的操作来判断是否存在0：bool hasNoZeroByte=((v&0xff)&&(v&0xff00)&&(v&0xff0000)&&(v&0xff000000));上面的操作相当于取 ...继续阅读 (12)

linux内核和其他一些开源的代码中，经常会遇到这样的代码：do{...}while(0)这样的代码一看就不是一个循环，do..while表面上在这里一点意义都没有，那么为什么要这么用呢？实际上，do{...}while(0)的作用远大于美化你的代码。查了些资料，总结起来这样写主要有以下几点好处：1、辅助定义复杂的宏，避免引用的时候出错：举例来说，假设你需要定义这样一个宏：#define DOSOMETHING()\ foo1();\ foo2();这个宏的本意是，当调用DOSOMETHING()时，函数foo1()和foo2()都会被调用。但是如果你在调用的时候这么写：if(a>0)DOSOMETHING();因为宏在预处理的时候会直接被展开，你实际上写的代码是这个样子的：if(a>0)foo1();foo2();这就出现了问题，因为无论a是否大于0，foo2()都会被执行，导致程序出错。那么仅仅使用{}将foo1()和foo2()包起来行么？我们在写代码的时候都习惯在语句右面加上分号，如果在宏中使用{}，代码里就相当于这样写了：“{...};”，展开后就是这个样子：if(a>0){ ...继续阅读 (12)

最近在优化一段代码的过程中，用到了gcc的内联汇编。代码中有用到了许多全局变量，比如：charmi[10]={...};开始的时候，我对全局变量的取址是这样的：__asm__("movq (%2, %1, 1 ), %0":"=r"(cookie):"r"(index),"r"(mi));在一个函数中使用这段代码，一条指令完成了对mi数组的访问，但同时也存在问题，即mi的地址会占用一个寄存器，mi的地址要在早先的时间内被装载到寄存器中（指令由编译器自动生成），同时，被mi占用的寄存器有些情况下不能被其他手工内联的汇编指令随便写入，编译器还没有那么智能帮你讲寄存器的内容保存好。综上，使用这种方法会存在两方面问题：1、使用至少两条指令来读取全局变量2、正确性要小心呵护。但是，在gcc的O2选项下访问mi变量的时候，因为全局变量的地址在编译时是可以确定的，所以这样的代码inttmp=mi[3];反汇编出来是mov0x405600(%eax),%ebx;其中，eax中存的是index，也就是3，ebx是tmp。0x405600是全局变量mi的地址，在编译时就确定了这个地址，所以直接写在指令中了。由于没系统的学过内联汇编的语法，所以不知道怎么在C语言中直接嵌入全 ...继续阅读 (18)

在做一些web相关的工作的时候，我们往往可能需要做一些对url的处理，其中包括对相似的url的识别和处理。这就需要计算两个url的相似度。那么怎么进行url相似度的计算的？我首先想到的是把一个url看作是一个字符串，这样就简化成两个字符串相似度的计算。字符串相似度计算有很多已经比较成熟的算法，比如“编辑距离算法”，该算法描述了两个字符串之间转换需要的最小的编辑次数；还有一些其他的比如“最长公共字串”等方法。但这些方法对于url相似度的计算来说是不是够了呢？比如给以下三个url：url1: www.spongeliu.com/xxx/123.htmlurl2: www.spongeliu.com/xxx/456.htmlurl3: www.spongeliu.com/xxx/abc.html这三个url的编辑距离是一致的，但是直观上我们却认为url1和url2更加相似一些。再比如我们要判断两个站点是否同一套建站模版建立的，抽出两个url如下这样：url1: www.163.com/go/artical/43432.htmlurl2: www.sina.com.cn/go/artical/453109.html这两个url按照情景应该是相似的，这就超出了字符串相似度判断的能力范围。重新回到问题，要判断的是两个url的相似度，但是字符串的判断方法又不能很好应用。那么url和字符串的区别在 ...继续阅读 (12)

熟悉C的人都知道，C语言支持可变参数函数(Variable Argument Functions)，即参数的个数可以是不定个，在函数定义的时候用(...)表示，比如我们常用的printf()\execl函数等；printf函数的原型如下：intprintf(constchar*format,...);注意，采用这种形式定义的可变参数函数，至少需要一个普通的形参，比如上面代码中的*format，后面的省略号是函数原型的一部分。C语言之所以可以支持可变参数函数，一个重要的原因是C调用规范中规定C语言函数调用时，参数是从右向左压入栈的；这样一个函数实现的时候，就无需关心调用他的函数会传递几个参数过来，而只要关心自己用到几个；以printf为例：printf("%d%s\n",i,s);printf函数在定义的时候，不知道函数调用的时候会传递几个参数。在实现上，printf函数只需关心第一个参数，即字符串“%d%s\n”，当读到%d的时候，printf知道自己需要第二个参数，这时只需要去栈上寻找即可；当读到%s时，再去栈上网上寻找一个参数即可。简单说，printf不关心栈上到底压了多少参数，只关心自己需要多少。那么对于一个定义为可变参数的函数，函数定义的时候并没有定义形参原型，怎么使用参数呢？C语言定义了一系列宏来完成可变参数函数参数的读取和使用：宏va_s ...继续阅读 (32)

很久以前，我接触的最初几本C语言书中，我记得有类似这么一句话“C语言是一种弱类型的语言，类型之间可以进行隐式的转换；而C++是强类型的语言，需要进行强制类型转换”。我忘了是哪本书，但这句话我一直记得。因为实际写代码中一直也没有触碰隐式的转换（我一般都会强制转换），所以也没有深究过这个问题。然而最近的一段代码却给我带来了一些困惑。copyright@ www.spongeliu.com先抛开我遇到的问题不说，简单回顾下C语言的隐式类型转换，如下一段代码：#includedoublesum(doublex,doubley);//声明一个函数intmain(){intx=10;inty=10;doublez=sum(x,y);printf("%lf\n",z);return0}没问题，我们得到的结果是20.000000。同时，上面代码中，首先声明了sum函数的原型“double sum(double x,double y);”。 熟悉C的人都知道，在“old style c”中，我们可以声明一个不带参数原型的函数，也就是这么声明“double sum()；” 这表示sum函数可能有无限个参数，具体由函数定义来决定。那么，如果在上述代码中使用这种方式会怎么样呢？doublesum();//声 ...继续阅读 (24)

在blogspot上看到一个十分有趣的字符串算法题目，原文在这里。作者讲述了自己面试google的一次经历。本文不理会这个故事，只来讨论一下里面着个有趣的算法。算法题目：有两个字符串由不同的字母组成，一长一短，长的为A短的为B。设计一个算法，如果所有在B中出现的字符都在A中出现，则返回true，否则返回false。例子：如下字符串：字符串A: abddfdioegdddffsfagj字符串B: dofsjadg字符串B中每个字符都在A中出现，返回true。如下字符串：字符串A: aaaabbbbbbdddddd字符串B: acc字符串B中有字符没在A中出现，返回false。这只是个很基础的算法题目，相信很多人都能够立刻想出答案。答案1：对字符串B中的每个字母在A中都遍历一遍。这个答案很烂，其时间复杂度为O(n*m)答案2：设一个哈希表，对字符串A的字符遍历，将每个字符对应的哈希表中的值设为1。然后对B中的字符进行遍历，如果所有字符对应的hash值都为1，则返回true，否则返回false。这个答案的时间复杂度是O(m+n)，应该是大多数面试者想要的答案，相信大多数人也能想到。这样结束了？如果真结束了，那就谈不上有趣了！如果我们对空间要求比较高该怎么办？答案3：我们可以观察到，字母总共就有26个，而且在上面答案中，hash表的值只有1和0两种情况。那就好办了，我们知道int类型是32 ...继续阅读 (21)

1、在安装openoffice过程中出现大致如下的错误ERROR: Error 65280 occurred while making /var/tmp/portage/app-office/openoffice-3.2.1-r1/work/ooo/build/OOO320_m19/desktop/zipintro rmdir /var/tmp/portage/app-office/openoffice-3.2.1-r1/temp/yERj5YXC9A make: *** [stamp/build] Error 1 * ERROR: app-office/openoffice-3.2.1-r1 failed: * Build failed * * Call stack: * ebuild.sh, line 54: Called src_compile * environment, line 8141: Called die * The specific snippet of code: * make || die "Build failed" * * If you need support, post the output of 'emerge --info =app-office/openoffice-3.2.1-r1', * the complete ...继续阅读 (50)

这篇文章是一篇译文，跟上一篇文章相呼应的，原文在这里。对于结构体和空类大小是1这个问题，首先这是一个C++问题，在C语言下空结构体大小为0(当然这是编译器相关的)。这里的空类和空结构体是指类或结构体中没有任何成员。在C++下，空类和空结构体的大小是1（编译器相关），这是为什么呢？为什么不是0？这是因为，C++标准中规定，“no object shall have the same address in memory as any other variable” ，就是任何不同的对象不能拥有相同的内存地址。如果空类大小为0，若我们声明一个这个类的对象数组，那么数组中的每个对象都拥有了相同的地址，这显然是违背标准的。但是，也许你还有一个疑问，为什么C++标准中会有这么无聊的规定呢？当然，这样规定显然是有原因的。我们假设C++中有一个类型T，我们声明一个类型T的数组，然后再声明一个T类型的指针指向数组中间某个元素，则我们将指针减去1，应该得到数组的另一个索引。如下代码：1 2 3 4 5T array[5];intdiff=&array;[3]-&array;[2];// diff = 1上面的代码是一种指针运算，将两个指针相减，编译器作出如下面式子所示的动作：diff = ((char *)&array;[3] - (char *)&ar ...继续阅读 (14)

熟悉c的人都知道，sizeof是一个关键字而不是一个宏或者库函数什么的，他的值是在编译时确定的，如果这个不了解，可以现看看这篇文章和这篇文章。 既然如此，让我们先看下面几个小例子：sizeof(int);sizeof(char);sizeof(double);上面三行sizeof的值是多少呢？这里我们假定在32位的x86系统下。我们会得到答案：4，1，8。这个没什么吧，大多数人都应该知道。那么，下面这个：sizeof(int);sizeof(long);在32位x86下，这两个是多少呢？4，8？实际上，答案是4，4。我们需要注意，long类型在32位系统下是32位的。那么，64位下结果又如何呢？8，8？其实答案是4，8。另一个需要注意的是，64位下的int是32位的。上面只是热热身，现在，让我们看sizeof的下面几种情形：1、sizeof一个结构体。这个我就不说啥了，具体的参考这篇文章。至于空的结构体，下面会解释。2、sizeof数组、指针等先看下面两个例子：chara[100];charb[100]="helloworld!";charc[]="helloworld!";char*d=b;sizeof(a);sizeof(b& ...继续阅读 (17)