__builtin_popcount(x) & lowbit(x)
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
输入 个整数 ,求它的二进制表示形式中有多少个 。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int x;
cin >> x;
cout << __builtin_popcount(x) << endl;
return 0;
}
函数太难记？没关系，我们有
操作每次减去 的二进制表示形式中最后一个 。，大家可能会误以为时间复杂度为 ，(因为一个整数 二进制表示形式最多有 位)，其实时间复杂度为 ， 是 的二进制形式中 的数量，最坏情况下，即全为 时退化为 ，算法效率极高。
#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;
}
输入格式
共一行，包含一个正整数 。
输出格式
输出它的二进制表示形式中有多少个 。
数据范围
输入样例：
3
输出样例：
2