(位运算) $O(logn)$

C++ 代码

#include <cstdio>

using namespace std;

const int N = 20;
int c[N] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0}; // 0~15 的16进制数字圈圈数量

int main() {
    int n;
    scanf("%d", &n);
    int res = 0;
    if (n == 0) res = 1;
    else {
        while (n) {
           int t = n & 15;
           res += c[t];
           n >>= 4;
        }
    }
    printf("%d\n", res);
    return 0;
}