用lowbit感觉有点多此一举，直接让x&=（x-1）就行了，效果就是每次都去掉末尾的1。根本不用得到之后再减去。

但是显然 lowbit 更好理解，无脑套就行了

妙啊

算法二的时间复杂度 $nlongn$ 是什么鬼？另外建议 log 写成 \log，比如 n \log n

有点想笑哈哈哈哈哈

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int res = 0;
        int x;cin >> x;
        for (int i = 32; i > 0; i --)
        {
            if (x >> i & 1) res ++ ;
        }
        cout << res << ' ';
    }
    return 0;
}

妙啊

能问一下为啥i从32开始吗

我也想问，有解答踢我谢谢

可能是因为数据范围32位

int类型4个字节、32位，一般应该从31到0移位判断，这个32开始好像有点问题。

第三十二位，是不是代表数的正负？

题目说了是正数，int类型最高位为0，应该也没啥问题

你这个题解似乎有问题，对于x=1的情况其实是符号位溢出随意才会判对了，i应该从31枚举到0，前闭后闭。

我的傻瓜做法

#include[HTML_REMOVED]

using namespace std;
const int N = 1e6+10;
int q[N], n;
int main(){
scanf(“%d”,&n);
for(int i = 0 ;i<n ; i++) scanf(“%d”,&q[i]);

for(int i = 0; i< n; i++){
    int sum = 0,m=q[i];
    while(m){
        if(m%2) sum++;
        m = m/2;
    }
    cout<<sum<<" ";
}
return 0;

}

好憨啊，hh

哈哈哈哈我也是这么写的

算法二对负数会死循环。

为什么会出现死循环呢？

负数 右移 是 补 1

感谢~ 负数右移最后会变成全一的状态，等于-1

确实

int bitwise(int x) {
    return x & -x;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
        int res = 0;
        while(arr[i]) {
            arr[i] -= bitwise(arr[i]);
            res++;
        }

这段代码的时间复杂度不是直接的 O(NlogN)。要准确地评估其时间复杂度，我们需要分析循环的结构以及 bitwise 函数的影响。

分析
外部循环：遍历 n 个元素，因此外部循环是 O(N)。
内部循环：每次循环执行 arr[i] -= bitwise(arr[i]);。这里的 bitwise 函数返回的是 x 的最低设置位（即，最低的非零位）的值。这意味着每次循环实际上将 arr[i] 中最右边的 1 变为 0。
对于每个元素 arr[i]，内部循环的次数取决于 arr[i] 中设置为 1 的位的数量，这通常称为该数的汉明权重或汉明距离。
时间复杂度的评估
最坏情况：如果 arr[i] 是一个较大的数，它的二进制表示中可能包含多个 1。在最坏的情况下，arr[i] 的二进制表示中的 1 的数量等于该数的位数。例如，对于一个 32 位的整数，最坏的情况是所有位都是 1，那么内部循环需要运行 32 次。
平均情况：如果假设 arr[i] 中的每一位有 50% 的概率是 1，则平均情况下 1 的数量是位数的一半。但实际上，通常不会这么多，特别是对于随机分布的整数。
综合评估
由于每个数的内部循环次数与该数二进制表示中 1 的数量成正比，而不是与数值的大小成对数关系，因此代码的整体时间复杂度是 O(N⋅k)，其中 k 是输入值中平均设置为 1 的位的数量。

对于大多数实际应用，特别是在随机数据上，我们可以近似地认为 k 是一个相对较小的常数（取决于数据的特性），从而可以认为这个时间复杂度接近 O(N)。如果考虑所有可能的位，即一个典型的整数可能的最大位数，那么这个复杂度可能看起来更接近 O(NlogM)，其中 M 是可能的最大数值。但是在大多数情况下，每个数中 1 的数量远小于其最大可能位数。 –GPT4

C++STL 六行搞定:

#include<bits/stdc++.h>
using namespace std;
#define out(x) for(int i = 0; i < x; i++)
int a[666666], n;
int main(){
    cin >> n; out(n)cin >> a[i]; out(n)cout << __builtin_popcount(a[i]) << " ";}

玩尬的是吧：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int arr[N];
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < N; ++i) {
        bitset<32> bst(arr[i]);
        cout << bst.count() << " " << flush;
    }
    return 0;
}

强行缩短行数~~

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    while (n -- ){
        int x;
        cin >> x;

        int cnt = 0;
        while (x) cnt += x&1, x >>= 1;
        cout << cnt << ' ';
    }
    return 0;
}

nice

暴力的是时间复杂度是对的，lowbit的时间复杂度不对吧，应该是O(n*M),M是数字中1的个数的平均值。

时间复杂度都是 $O(n)$ 吧

不是O(n), 因为这里的n表示的是数列的个数，即总共输入n个整数；但是对于其中每个整数x，转化成二进制后的长度为logx级别的；综合两者，时间复杂度为O(nlogn)

$\log x$ 怎么最后变 $\log n$ 了

两者都是位运算 ， 都是nlogn 何来暴力一说

hhhh,还有人吗？

第一天

x-=lowbit(x)怎么理解?

负数得不到正确结果吧

优秀，感谢帮助。你是大大的好人。

暴力不会超时吗

cin >> n;
while(n)
    if(n%2) res++;
cout << res;

#include<iostream>

using namespace std;

int main()
{
    int n,cnt,T; cin >> T;
    while (T --)
    {
        cnt = 0;
        cin >> n;
        while (n)
        {
            if (n & 1) cnt ++;
            n = n >> 1;
        }
        cout << cnt << ' ';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int arr[N];
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < N; ++i) {
        bitset<32> bst(arr[i]);
        cout << bst.count() << " " << flush;
    }
    return 0;
}

负数的补码，不是这样求的吗：负数的原码符号位不变，其他位取反，得到反码，反码再加1，得到补码，这里说-x=~x+1,怎么对呢

想出来了，谢谢大家。。，负数的原码就是正数的原码全部取反，然后加1，
这个和上面的说法其实做法都一样

感谢大佬！