AcWing 801. 二进制中1的个数（位运算）

# 二进制中 1 的个数 - 位运算

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

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++;
        cout << res << ' ';
    }
    return 0;
}

#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++; //每次减去x的最后一位;
        
        cout << res << ' ';
    }
    
    
    return 0;
}

# 位运算常用操作

n 的二进制表示第 k 位是几

1. 先把第 k 位移到最后一位 n >> k
2. 看个位是几 x & 1

1.2. 结合一下 n >> & 1
看一下 n 的二进制第 k 位是几

lowbit (x) 返回 x 的最后一位
x = 1010 lowbit (x) = 10
x = 101000 lowbit(x) = 1000

    x & -x = x & (~x + 1)
    x = 1010...100...0
  ~x = 0101...011...1

最后一位 1 的位置变成 0 之后全变 1
~x + 1 = 0101...100...0
取反 + 1 即最后一位 0 的位置变成 1
x & (~x + 1)= 0000...100...0
x & (~x + 1) 应该是最后 x 一位 1 接下来全是 0