C 语言第29题：统计整数二进制表示中 1 的个数

题目

从标准输入读入一个无符号整数 n，统计并输出其二进制补码表示中数字 1 的个数（汉明重量）。

输入格式：一行输入一个无符号整数 n。

输出格式：输出一个整数，表示其二进制中 1 的数量，末尾换行。

数据范围与约定：0 ≤ n ≤ 4×10⁹（32位无符号整数）。

思路与算法

1. 逐位右移检查
循环 while (n)，每次通过 cnt += n & 1 累加最低位的二进制状态，然后逻辑右移 n >>= 1。

2. Brian Kernighan 高效算法
进阶技巧：利用 n &= (n - 1) 每次直接抹去二进制最低位的 1，循环次数等于 1 的实际个数，效率比逐位扫描更高。

完整程序

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }

    int cnt = 0;
    // 逐位统计二进制 1 的个数：
    // n & 1 取出最低位的值，n >>= 1 逻辑右移推进下一位
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }

    printf("%d\n", cnt);
    return 0;
}

运行示例

输入：

13

输出：

3

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

Kernighan 计数

程序：

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }
    int cnt = 0;
    while (n) {
        n &= n - 1;
        cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

输入：

13

输出：

3