程序面试试题（节选）

lwevil

typ77: Re: Re:程序面试试题（节选）


这个题目是靠算法的问题。如果连你认为这么简单的算法也不能写出来，到底是你水平问题还是出题人水平问题...

考汇编？ 那怎么不考10101010101010。。。的机器语言？ 干脆考硬件算球了，反正速度快三！ 什么叫“高效”？ 在算法相同的情况下，机器语言就高效。

要不下次出题： 1+2+3+。。。+100， 如何高效的写出这个算法，说明复杂度和思想（提示： 不能使用公式：(1+n)/2 ）

好题！好题啊！ [em23]

euclid

关于glibc中的strlen的高效实现是这样的，它是一次跨越4个字节的检查。
int strlen (const char * s)
{
    DWORD* t = (DWORD*)s;
    int len = 0;

    while (*t所有位不全为0) { //这里有一个位操作技巧，用来检查*t中是否有0字节，如果有，就判断第几字节是0，做收尾工作
        t++;
        len += 4 ;
    }
}

ricohcanon

哇哇~~~看了本帖偶已然是晕菜了，各位是公说公有理，婆说婆有理，出现N多个版本，到底哪个版本是正解啊？有没有权威站出来说一句啊？最好那个游戏公司出题的大侠把楼主所有题目都给出个正确答案来，以偶等便学习之。

tarkey

  while (*t所有位不全为0) { //这里有一个位操作技巧，用来检查*t中是否有0字节，如果有，就判断第几字节是0，做收尾工作


偶倒是很感兴趣,这个操作是什么样的.

FlyMagic

euclid: Re:程序面试试题ń谘。?/b]

关于glibc中的strlen的高效实现是这样的，它是一次跨越4个字节的检查。
int strlen (const char * s)
{
...

还没办法理解这个算法的奥秘，它到底是怎样做的？
那个位操作是什么样的位操作啊？

FlyMagic

我能想出来的就是这个了。
if (t & 0xFF000000 && t & 0x00FF0000 && t & 0x0000FF00 && t & 0x000000FF)

的确，根据优先处理的原则，只要查出一个false，就可以跳过下面的，所以，if运算的数量不会增加。而且，因为是四字节步进的，每次循环中可以减少6次加法（递增和计数各3次）运算。理论上应该比单字节循环要快吧。

FlyMagic

另外，t++是不对的。在这种情况下，编译器会保留一个t的副本（详细请见关于C++后置运算），造成性能的下降。使用++t会更快，因为只要计算一次。

FlyMagic

int strlen (const char * s)
{
    DWORD * t = (DWORD*)s;
    DWORD * t1 = (DWORD*)s;

    while (*t所有位不全为0) { //这里有一个位操作技巧，用来检查*t中是否有0字节，如果有，就判断第几字节是0，做收尾工作
        t++;
    }
    int len = t - t1; // 通过计算指针的距离，省去了循环中的计数计算，这样能优化吗？
}

谜の名侦探

有个汇编指令好像是检测位的，不过不记得了，属于比较生僻的指令

euclid

/* 这个strlen采用4字节一步的方法遍历字符串（因为现代机器上32位操作最快），每一步都判断有没有0字节 */
size_t strlen (const char *str)
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, himagic, lomagic;
/* 下面这一块是先把指针走到地址是4的倍数的地方，再开始遍历。'& (sizeof (longword) - 1)) '相当于char_ptr % 4 */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

/* 这里用一个long指针接管char指针 */
  longword_ptr = (unsigned long int *) char_ptr;

  himagic = 0x80808080L;
  lomagic = 0x01010101L;

  for (;;)
    {
      longword = *longword_ptr++;
      /* 下面这个方法很厉害，用来检测当前4字节中有无0字节。下面再说 */
      if (((longword - lomagic) & himagic) != 0)
    {
      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      }
    }
}

(longword - lomagic) & himagic =
  longword
- 00000001 00000001 00000001 00000001
& 10000000 10000000 10000000 10000000
这算是一种并行方法吧，把4个字节同时算。那只要看一个字节就行了。
就是说把1~127的字节都抹成0,而把0变成非0...