C/C++：两个小题目

1、给定一个unsigned int数n，写一个函数计算其二进制中“1”的个数（n=0，则结果为0，n=1则结果为1，n=5则结果为2）。函数原型为：int CountBits(unsigned int n);假定在32-bit机器上运行。

乍一看，也忒简单了：
int CountBitsWithSTL(unsigned int n)
{
    return bitset< 8 * sizeof n > (n).count();
}

哈哈，顺利完成！然后后续的问题又来了：不能使用STL！于是，憋了半天，想到了移位操作和mod。当一个数的二进制末位为0，则该数mod 2的结果永远是0，所以只要n % 2 != 0就表示末位是1。算完末位之后，将n右移一位，在计算n % 2，依次类推，直到n为0，因此可以写出：
int CountBits(unsigned int n)
{
    int count = 0;
    while (0 != n)
    {
        if (0 != n % 2)
            ++count;
        n >>= 1;
    }
    return count;
}

看来也不难。后面又有一句：尝试使用最少的循环。晕！思来想去不知道怎么解答。这里面的循环次数已经够少了，最多才32次。不知道那位大虾有好办法指点一下——据说可以使用查询表，以空间来换取时间。如果查询表已经populated，存放在Bits[]中，那么简单了：
int CountBitsLookupTable(unsigned int n, int Bits[])
{
    return Bits[n];
}
不知道对不对……

2、反转一个字符串，使用C语言。由于使用C语言，C++字符串的那些东东就没法用了！不过还是难不倒我，随手就来——先把这个字符串从尾到头拷贝到临时空间，然后再拷贝回来：
char * ReverseStringSlow(char * aStr)
{
    int len = strlen(aStr);
    char * ptemp = (char*) malloc (len);
    for (int i = len - 1, j = 0; i >= 0; --i, ++j)
    {
        ptemp[j] = aStr[i];
    }
    strncpy(aStr, ptemp, len);
    free(ptemp);
    return aStr;
}

注意这里起的名字，这说明这个函数还有改进的可能。一个算法的两个特性是时间、空间。这个函数既占空间（多用len个字节），又费时间（2 * len次循环，因为strncpy也是循环，还得考虑函数调用的开销）。当然，在现在的PC上这些根本就可以忽略不计。然而，在资源非常有限的手持设备上，影响比较显著。在实时系统上更甚，尤其是len非常大的时候。 于是仔细想了想，我可以根据对称性来交换字符——因为“abcde”反转相当于“a”和“e”对调，“b”和“d”对调，“c”保持不动。那么可以把字符串分成两半，依照对称性对调就OK了。于是得出了下面这个：
char * ReverseStringFast(char * aStr)
{
    int len = strlen(aStr);
    char temp = '\0';
    for(int i = 0; i < len / 2; ++i)
    {
        temp = aStr[i];
        aStr[i] = aStr[len - i - 1];
        aStr[len - i - 1] = temp;
    }
    return aStr;
}

这时，只需要额外的一个字节，循环次数也变成了len/2次，快了不少啊。再往下看题：现在不要考虑其他，用C，递归方式反转。开始头大了……

想了好久也没有眉目——也许是被前两个函数的原型给束缚住了思维吧，实在忍不住了，上网查了一下，居然没有合适的——他们都是直接在reverse时输出，旧的字符串依然保持原来的顺序。不过看了一些之后，思路有些打开了——我改一下函数原型不就简单多了吗？如：
void ReverseStringRecursively(char * begin, char * end);

如此一来，就好办多了：
void ReverseStringRecursively(char * begin, char * end)
{
    if (begin >= end)
        return;
    char temp = *begin;
    *begin = *end;
    *end = temp;
    return ReverseStringRecursively(++begin, --end);
}

总算是完成了~~~ 看来我这基本功还有待历练啊！对于自己的信心确实是一个不小的打击。这两道题虽然简单，但深究起来，还是有不少东西值得琢磨的。

PS：在ReverseStringSlow()中没有释放内存，居然没有人提到这个问题……还是我自己发现给改回来了。

Copyleft (C) 2007, 2008 raof01. 本文可以用于除商业用途外的所有用途。若要用于商业用途，请与作者联系。