用C語言實現遞歸函數的位運算

代碼中有兩個問題：

• 當設置了2個低位中的一個時，立即返回0。這是不正確的。如果參數為0，則應返回0；如果2個低位為非0，則應添加一個遞歸值。
• 遞歸時將abcCode轉換為(unsigned)，這可能會掩蓋最重要的位。你應該改用(unsigned long)。

以下是一個修改版本：

int abcLength(long abcCode) {
    int n = 0;
    if (abcCode == 0)
        return 0;
    if (abcCode & 3)
        n++;
    return n + abcLength((unsigned long)abcCode >> 2);
}

這可以混淆為：

int abcLength(long code) {
    return code ? !!(code & 3) + abcLength((unsigned long)code >> 2) : 0;
}

下面是一個帶循環的解決方案：

• 在偶數和奇數位置合并位
• 迭代以計算具有低位集的字節數

Simple implementation:

int abcLength(long x) {
    unsigned long code = x;
    int n;
    for (n = 0; code != 0; code >>= 2) {
         if (code & 3)
            n++;
    }
    return n;
}

這是一個沒有任何循環的可能更快的方法：

int abcLength(long code) {
    code = (code | (code >> 1)) & 0x5555555555555555;
    code = (code + (code >> 2)) & 0x3333333333333333;
    code = (code + (code >> 4)) & 0x0F0F0F0F0F0F0F0F;
    return (code * 0x101010101010101) >> 56;
}