C 語言遞迴函數計算二進位中 1 的個數：主函數呼叫與回傳值處理完整範例

題目需求

撰寫 Count_One_Bits(n) 遞迴函數計算整數 n 二進位表示中 1 的個數，主函數輸入輸出。

完整程式碼

#include <stdio.h>

int Count_One_Bits(unsigned int n) {
    if (n == 0) return 0;
    return (n & 1) + Count_One_Bits(n >> 1);
}

int main() {
    unsigned int n;
    printf("輸入非負整數: ");
    if (scanf("%u", &n) != 1) return 1;
    int count = Count_One_Bits(n);
    printf("二進位中 1 的個數: %d\n", count);
    return 0;
}

遞迴邏輯解析

• n & 1 取最低位（0 或 1）。
• n >> 1 右移一位，遞迴處理剩餘位。
• 基準情況 n == 0 回傳 0，終止遞迴。

非遞迴替代方案（效能更佳）

int Count_One_Bits_Iter(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
// 或使用內建：__builtin_popcount(n) (GCC/Clang)

常見錯誤修正

• 原始碼缺少 return count; 導致函數無回傳值。
• 主函數未接收回傳值直接列印。
• 參數型別建議 unsigned int 避免負數右移行為未定義。

總結

遞迴函數 Count_One_Bits 以 (n&1) + Count_One_Bits(n>>1) 計算 1 的個數，主函數負責輸入、呼叫、輸出。注意基準情況與回傳值傳遞。