统计0~n置位总数的countSetBits递归函数触发段错误原因求解

你的代码触发段错误的核心诱因是C语言运算符优先级理解错误，导致递归逻辑完全错乱，最终引发栈溢出：

• 条件判断逻辑完全失效
  你写的判断语句if ( (n + 1) & n == 0 )意图是检测n是否为2的幂减1，但C语言中==优先级高于按位与&，该语句实际执行的是(n + 1) & (n == 0)，和你的预期逻辑((n + 1) & n) == 0完全不符，递归终止条件无法正常触发。
• 移位运算相关的所有表达式计算结果全部错误
  你设计的逻辑需要优先计算1 << b再做加减运算，但C语言中加减运算符优先级高于移位运算符<<，所有相关表达式解析结果都不符合预期：
  • 1<<b - 1实际解析为1 << (b - 1)，而非你预期的(1 << b) - 1
  • n - 1<<b实际解析为(n - 1) << b，而非你预期的n - (1 << b)
  • n - 1<<b + 1实际解析为(n - 1) << (b + 1)，而非你预期的n - (1 << b) + 1
• 上述错误会导致递归传入的参数出现负数、远大于预期的异常值，永远无法命中n == 0的终止条件，递归调用栈持续膨胀超出系统栈大小限制，最终触发栈溢出，表现为segmentation fault。

修正后的参考代码 #

int countSetBits(int n)
{
    if (n == 0)
        return 0;
    int b = floor(log2(n));
    if ( ((n + 1) & n) == 0 ) {
        return (1 << b) * (b + 1); // 这里log2(n+1)等价于b+1，直接复用变量更高效
    }
    return (n - (1 << b) + 1) + countSetBits(n - (1 << b)) + countSetBits((1 << b) - 1);
}

内容的提问来源于stack exchange，提问作者Ayush Kasara