使用C的递归函数中的按位运算

Question

所以我对使用 C 还很陌生，我正在参加一个在线课程，该课程为我提供练习。

我想做的是采用 long 数据类型和 return 根据它的二进制表示形式的 int 值。规则是，如果最右边的 2 位不为零（01、10、11），则将其计为 1 并移至下 2 位，依此类推。例如：

00000000-00000000-00000000-00000001- 应该 return 1.

00000000-00000011-00000001-00000010-应该return 3.

00001000-11000011-00001001 -00110010-应该return7.

int abcLength(long abcCode) {
  if(abcCode&3) {   /*** <--- Try to do this using only bitwise and logical operators !  ***/
    return 0;
  }
  return 1 + abcLength((((unsigned)abcCode>>2)); /*** <--- Try to do this using only bitwise and logical operators !  ***/
}

问题是我不知道如何处理二进制字符串中间有 00 的情况。他们告诉我只使用一个 if 语句，但现在它应该算作 00。

关于如何使这项工作有任何想法吗？

Answer 1

你的代码有两个问题：

你 return 0 立即设置 2 个低位之一。这是不正确的。如果参数为 0，你应该 return 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;
}

这是一个带循环的解决方案：

合并偶数和奇数位置的位
迭代以计算设置了低位的字节数

简单实现：

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;
}

使用C的递归函数中的按位运算

bitwise operations in recursive function using C

c

recursion

bit-manipulation

bitwise-operators