递归统计二进制1的个数函数出现Segmentation Fault问题求助

Hey there! Segmentation faults (segfaults) in recursive functions almost always boil down to infinite recursion blowing the call stack or invalid memory access. Let's walk through the most common issues with your recursive bit-counting function and how to fix them.

Common Causes & Fixes #

1. Missing or Incorrect Termination Condition #

This is the #1 culprit for segfaults here. If your function doesn't stop when there are no more 1 bits left to count, it will keep calling itself until the stack runs out of space.

Example of a Broken Function:

int count_ones(int n) {
    // No stop condition! When n hits 0, it still recurses
    return 1 + count_ones(n & (n - 1));
}

When n becomes 0, n & (n-1) stays 0, so the function calls itself forever—triggering a segfault once the stack overflows.

Fixed Version (Add Termination):

int count_ones(int n) {
    if (n == 0) {
        return 0; // Stop recursion when no more 1 bits exist
    }
    return 1 + count_ones(n & (n - 1));
}

2. Handling Negative Numbers (Signed Integer Edge Case) #

If your function takes a signed int and you pass a negative number, things break. On most systems, negative numbers use two's complement, where the highest bit is set to 1. For example, -1 is represented as all 1s in binary. When you run n & (n-1) on -1, you get -2, then -4, and so on—this never reaches 0, leading to infinite recursion and a segfault.

Fix: Use Unsigned Integers

Change your parameter type to unsigned int to avoid negative number pitfalls:

int count_ones(unsigned int n) {
    if (n == 0) {
        return 0;
    }
    return 1 + count_ones(n & (n - 1));
}

If you need to handle signed int inputs, cast to unsigned first:

int count_ones(int n) {
    unsigned int num = (unsigned int)n; // Convert to unsigned to safely handle negatives
    if (num == 0) {
        return 0;
    }
    return 1 + count_ones(num & (num - 1));
}

3. Debugging Tips to Confirm the Issue #

• Add print statements inside the function to track the value of n each recursion:

  int count_ones(int n) {
      printf("Current n: %d\n", n); // Check if n ever hits 0
      if (n == 0) {
          return 0;
      }
      return 1 + count_ones(n & (n - 1));
  }
  

  If you see n looping between negative values or never reaching 0, you know infinite recursion from unhandled negatives or missing termination is the problem.

• Use a debugger like gdb to inspect the call stack when the segfault happens. You'll see hundreds of repeated calls to count_ones, confirming infinite recursion.

Final Notes #

Recursive bit counting is totally valid, but you have to be strict about termination conditions and handle signed vs unsigned edge cases. The fixes above should resolve your segfault.

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