AcWing 801. 二进制中1的个数

题目传送门

一、前导知识

位运算两个性质：

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

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

三、练习x&(x-1)

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\)。

2.判断一个数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 <bits/stdc++.h>

using namespace std;

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--) {
        int cnt = 0;
        int x;
        cin >> x;
        while (x) x -= (x & -x), cnt++;
        printf("%d ", cnt);
    }
    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;
}