[C++知识库]位运算（二进制中1的个数）

位运算最常用的两种操作：

1.求整数n二进制表示中第k位（从个位开始算）数字是几：n>>k&1

• 先把第k位数字移到最后一位? n>>k
• 再看一下个位是几? ? x&1

2.lowbit操作：

lowbit(x)作用是返回x的最后一位1。例如：x=1010，lowbit(x)=10；x=101000,lowbit(x)=1000。

应用是统计x里面1的个数

题目：

?代码：

#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的最后一位1
        cout<<res<<' ';
    }

    return 0;
}

有关算法竞赛的题目会继续更新，欢迎评论交流！