位运算模板

模板

lowbit(x)是x的二进制表达式中最低位的1所对应的值。

比如，6的二进制是110，所以lowbit(6)=2。

最近回头看树状数组，发现关于lowbit()函数，目前有两种算法。

第一种是比较常见的，也是我一直在用的：

1
2
3
4
int lowbit(int x)
{
    return x&(-x);
}

最近发现了另一种算法，如下所示：

1
2
3
4
5
int lowbit(int x)
{
    return x&(x^(x-1));
}

两种算法的结果都是对的。
相比之下，第一种算法利用了负整数的补码特性，非常的巧妙，而第二种算法用另外一种方式计算出了最低位，其思想跟补码的也很相似。当然还是推荐第一种，不仅巧妙而且好记。

题目描述：

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式
第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围

1≤n≤100000,
0≤数列中元素的值≤109

输入样例：

```1 2 3 4 5

输出样例：

1 1 2 1 2

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
#include<iostream>

using namespace std;

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

int main(){
    int n;
    cin >> n;
    while(n--){
        
        int x;
        cin >> x;
        
        int res = 0; //计算二进制数中又几个1
        while(x){
            x -= lowbit(x), res ++;
            
        }
    cout << 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
#include<stdio.h>

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


int main(){
    int n;
    scanf("%d",&n);
    
    while(n--){
        int x;
        scanf("%d",&x);
        
        int res = 0;
        while(x){
            x -= lowbit(x);
            res ++;
        }
        
        printf("%d ",res);
    }
    
    return 0 ;
}