【題目鏈接】Neko Performs Cat Furrier Transform
【題目分析】要求將一個數字變成2n-1,通過嘗試我們發現如果將最低位的全零位和對應的全一數字（例如11000對應的就是111）異或那么數字就會變成想要的結果（11111）
但是如果前面還有0（比如110100）那么過程應該如下：110100^000011變成110111加一后變成111000然后就會得到結果，總之我們需要做的就是不斷將末尾的全零變成全1，然后在加一的時候就會進位將前面的0消滅
為了檢驗是否已經得到結果，我們不妨預處理一個所有結果的數組，然后在數組中用lower_bound和upper_bound找
尾部的全零位的查找可以借鑒樹狀數組中最低位1lowbit(x)=x&(-x)，最低位1后面全都是0，因此全零對應的的全一數字為lowbit(x)-1
#include<cstdio>
#include<algorithm>
using namespace std;int s[50];
int cnt=0;
int check[30];bool find(int x)
{//printf("test : lower_bound(check,check+30,x)-check=%d\n",lower_bound(check,check+30,x)-check);//printf("test : upper_bound(check,check+30,x)-check=%d\n",upper_bound(check,check+30,x)-check);if(lower_bound(check,check+30,x)-check==upper_bound(check,check+30,x)-check)return false;elsereturn true;
}
int work(int x)
{return (x&(-x))-1;
}
int main()
{for(int i=0;i<30;i++){check[i]=(1<<i)-1;}int x,y,ans=0;scanf("%d",&x);while(ans<40){//printf("test x=%d\n",x);y=work(x);//printf("test y=%d\n",y);s[cnt++]=lower_bound(check,check+30,y)-check;x=x^y;//printf("test x=%d\n",x);ans++;if(!find(x)){//printf("test x=%d\n",x);x++;ans++;}else{break;}}printf("%d\n",ans);for(int i=0;i<cnt;i++){printf("%d ",s[i]);}return 0;
}
