位运算（超详细）

二进制中1的个数

算法思想：lowbit（x）的实现就是x与-x做&运算。数a的负数的二进制表示是取反再加1，a&(-a)即等于a&（~a+1),就等于a的最后一位。

#include
#include
#include
#include

using namespace std;

const int N=1e5;

int q[N];

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

int main(){

    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];

    for(int i=0;i<n;i++){
        int res=0;
        while(q[i]){  //直到当前处理的这个数为0时，跳出循环。
            q[i]-=lowbit(q[i]); //每次都利用lowbit减去最低位的那个1
            res++;   //每减去1个1都要计数。
        }
        printf("%d ",res);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33