[编程笔记]-Lowbit取最小1

前言

lowbit是树状数组的基础啊，其重要性可想而知。

模板

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

演算

众所周知，在二进制中，-a等同于~a+1（a的值取反再加一）

a取反后，所有1变成0，0变成1，因此在原数中第一个1出现前，全都是1。

故而，再加上一个一，第一个1前面全部变成0，第一个1本来取反变成0了，进位又变回1，然后就结束了，它后面的数字照样是原数取反的结果。

这时候进行与运算，那么a中第一个1前面的全都是0，-a中第一个1前面的也全都是0，新数就全是0；

第一个1后面的全都和原数取反，所以在新数中也是0。故而，就得到了第一个1组成的新数。

举例：

a=1010011000
a=0101100111
-a=a+1=0101101000
a&-a=1010011000&0101101000=0000001000

例题

AcWing801-二进制中1的个数

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

const int N=1e5+5;

int n;
int a,ans;

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

int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d",&a);
        ans=0;
        while(a){
            a-=lowbit(a);
            ans++;
        }
        printf("%d ",ans);
    }
    return 0;
}

完结撒花o(￣︶￣)o