位运算

二进制第k位上的数字是几

n >> k & 1

获取n的二进制表示

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a = 10;
    for(int i = 3;i >= 0;i--) {
        cout << (a >> i & 1) << endl;
    }
    return 0;
}

lowbit函数的引入

lowbit函数主要是用来获取最后一个1，即以后的位数

比如n = 10100， lowbit(n) -> 100

实现方式

前提条件：~x + 1等价于 -x

我们是通过x & (~x + 1) 来实现(等价于x & -x)

比如x 为 10001000去反后的结果为01110111 ，这个时候再加上一相当于对最后一个0及以后进行去反 -> 01111000 最后去&操作，x最后一个1后面位值都是一样的保持不变，前面的都不一样则为0，最终结果也就是00001000

例题

输入n个数，求解每一个数二进制位中1出现的个数

#include <bits/stdc++.h>
using namespace std;

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


int main(){
    int n,t,cnt;
    cin >> n;
    while(n--) {
        cin >> t;
        cnt = 0;
        while(t) {t -= low_bit(t); cnt++;}
        
        cout << cnt << " ";
    }
    cout << endl;
    return 0;
}