python/TangDou/AcWing/BIT/801.md

##AcWing 801. 二进制中1的个数

一、题目描述

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

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

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

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

数据范围 1≤n≤100000,0≤数列中元素的值≤10^9

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

二、前导知识

位运算两个性质：

• x\&(-x)：保留二进制下最后出现的1的位置，其余位置置0

• x\&(x-1)：消除二进制下最后出现1的位置，其余保持不变

三、练习x\&(x-1)

求下面函数的返回值 (微软)

int func(x) { 
    int countx = 0; 
    while(x){ 
          countx ++; 
          x = x & (x-1); 
     } 
    return countx; 
} 

功能：将x转化为2进制，看含有的1的个数。

注: 每执行一次x = x\&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。

判断一个数x是否是2的n次方

#include <bits/stdc++.h>
int func(int x){
    if((x & (x-1)) == 0)
        return 1;
    else
        return 0;
}
 
int main(){
    int x = 8;
    printf("%d\n", func(x));
    return 0;
}

思路 如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0。

四、利用 x\&-x

#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;
        while (x) x -= lowbit(x), res++;

        printf("%d ", res);
    }
    return 0;
}

五、利用 x \& (x-1)

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int cnt = 0;
        int x;
        cin >> x;
        while (x) {
            x = x & (x - 1);
            cnt++;
        }
        printf("%d ",cnt);
    }
    return 0;
}

六、遍历每一个二进制位

#include <bits/stdc++.h>

using namespace std;

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