位运算

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

n >> k & 1 n 右移 k 位后和 1 做&运算

lowbit 操作 树状数组的基本操作

lowbit(x)作用是返回 x 的最后一位 1

x = 1010 -> lowbit(x)=10,x=101000 -> lowbit(x)=1000

lowbit 如何实现？ $x \& -x$,原理如下图:

可以用来统计 x 里面 1 的数量

思想: 每一次减去 x 里面最后一个 1(减 lowbit(x))，减了几次就有几个 1

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin >> arr[i];
    
    int num=0;
    for(int i=0;i<n;i++)
    {
        num =0;
        while(arr[i]!=0) 
        {
            arr[i] -= lowbit(arr[i]);
            num++;
        }
        cout << num << " ";
    }
    
    return 0;
}