清华大学慕课中讲的，侵删

0001 /******************************************************************************************
0002  * Data Structures in C++
0003  * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
0004  * Junhui DENG, deng@tsinghua.edu.cn
0005  * Computer Science & Technology, Tsinghua University
0006  * Copyright (c) 2003-2019. All rights reserved.
0007  ******************************************************************************************/
0008 
0009 #define POW(c) (1 << (c)) //2^c
0010 #define MASK(c) (((unsigned long) -1) / (POW(POW(c)) + 1)) //以2^c位为单位分组，相间地全0和全1
0011 // MASK(0) = 55555555(h) = 01010101010101010101010101010101(b)
0012 // MASK(1) = 33333333(h) = 00110011001100110011001100110011(b)
0013 // MASK(2) = 0f0f0f0f(h) = 00001111000011110000111100001111(b)
0014 // MASK(3) = 00ff00ff(h) = 00000000111111110000000011111111(b)
0015 // MASK(4) = 0000ffff(h) = 00000000000000001111111111111111(b)
0016 
0017 //输入：n的二进制展开中，以2^c位为单位分组，各组数值已经分别等于原先这2^c位中1的数目
0018 #define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c))) //运算优先级：先右移，再位与
0019 //过程：以2^c位为单位分组，相邻的组两两捉对累加，累加值用原2^(c + 1)位就地记录
0020 //输出：n的二进制展开中，以2^(c + 1)位为单位分组，各组数值已经分别等于原先这2^(c + 1)位中1的数目
0021 
0022 int countOnes2 ( unsigned int n ) { //统计整数n的二进制展开中数位1的总数
0023    n = ROUND ( n, 0 ); //以02位为单位分组，各组内前01位与后01位累加，得到原先这02位中1的数目
0024    n = ROUND ( n, 1 ); //以04位为单位分组，各组内前02位与后02位累加，得到原先这04位中1的数目
0025    n = ROUND ( n, 2 ); //以08位为单位分组，各组内前04位与后04位累加，得到原先这08位中1的数目
0026    n = ROUND ( n, 3 ); //以16位为单位分组，各组内前08位与后08位累加，得到原先这16位中1的数目
0027    n = ROUND ( n, 4 ); //以32位为单位分组，各组内前16位与后16位累加，得到原先这32位中1的数目
0028    return n; //返回统计结果
0029 } //32位字长时，O(log_2(32)) = O(5) = O(1)

C++ 代码

#include <cstdio>

using namespace std;

#define POW2(c) (1 << (c))
#define MASK(c) (((unsigned int) -1) / (POW2(POW2(c)) + 1))
#define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW2(c) & MASK(c)))

int countOnes(unsigned int x) {
    x = ROUND(x, 0);
    x = ROUND(x, 1);
    x = ROUND(x, 2);
    x = ROUND(x, 3);
    x = ROUND(x, 4);
    return x;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);

        printf("%d", countOnes(x));
        if (i != n) {
            printf(" ");
        }
    }
    return 0;
}