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

题目

统计整数二进制表示中 1 的个数

思路

本题统计整数二进制表示里 1 的个数（popcount）。

循环直到 n 为 0：每次 cnt += n&1，再 n>>=1。若涉及负数，需按题目约定转成无符号再数。

解题分析

逐位右移统计最低位是否为 1，循环 32 次对 unsigned 足够。另一种写法：n &= n-1 消去最低 1，计数次数即 1 的个数（Brian Kernighan）。

完整程序

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }
    int cnt = 0;
    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