1.Take a single 1.
i&-i The value returned is the number from the last forward to the first 1.
int work(int x){int num=0;for(;x;x-=x&-x) num++;return num;}
e.g.:luogu 1582Water reverse
#include<bits/stdc++.h> using namespace std; int n,k,ans; inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f;} inline int sudo(int i){int ans=0;for(;i;i-=i&(-i)) ans++;return ans;} int main(){ n=read();k=read(); while(sudo(n)>k) ans+=n&(-n),n+=n&(-n); printf("%d\n",ans);return 0;}
2.State compression: using binary numbers to represent sets.
UVa 11825
#include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f;} const int N=18; int p[N],s[N],cover[1<<N],f[1<<N]; int kase,n; int main(){ while(scanf("%d",&n)!=EOF&&n){ memset(p,0,sizeof p); memset(s,0,sizeof s); memset(cover,0,sizeof cover); memset(f,0,sizeof f); for(int i=0;i<n;i++){ int m,x; scanf("%d",&m); p[i]=1<<i; while(m--){scanf("%d",&x);p[i]|=(1<<x);}} int ALL=(1<<n)-1;//Representative for all numbers//sRepresentative number, cover[s] stands for PI under I. for(int s=0;s<=(1<<n)-1;s++){//All possible collections cover[s]=0; for(int i=0;i<n;i++) if(s&(1<<i)) cover[s]|=p[i];} for(int s=1;s<=(1<<n)-1;s++){ f[s]=0; for(int s0=s;s0;s0=(s0-1)&s) // s0-1Looking down, bitwise and finding subset if(cover[s0]==ALL) f[s]=max(f[s],f[s^s0]+1); //State transfer, exclusive or exclusion of the situation. } printf("Case %d: %d\n",++kase,f[ALL]); }return 0; }