题目描述

输入 $1$ 个整数 $x$ ,求它的二进制表示形式中有多少个 $1$。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << __builtin_popcount(x) << endl;
    return 0;
}

函数太难记？没关系，我们有 $lowbit。$

$lowbit$ 操作每次减去 $x$ 的二进制表示形式中最后一个 $1$。，大家可能会误以为时间复杂度为 $O(logn)$ ，(因为一个整数 $n$ 二进制表示形式最多有 $\lceil logn \rceil$ 位)，其实时间复杂度为 $O(k)$ ，$k$ 是 $x$ 的二进制形式中 $1$ 的数量，最坏情况下，即全为 $1$ 时退化为 $O(logn)$ ，算法效率极高。

#include<iostream>
using namespace std;
int lowbit(int x)
{
    int ans = 0;
    for (int i = x; i; i -= i & -i) ans ++;
    return ans;
}
int main()
{
    int x;
    cin >> x;
    cout << lowbit(x) << endl;
    return 0;
}

输入格式

共一行，包含一个正整数 $x$ 。

输出格式

输出它的二进制表示形式中有多少个 $1$。

数据范围

$1 ≤ x ≤ {10}^5$

输入样例：

3

输出样例：

2