This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of Zephyr's existence know very little about her. For example, no one has any clue as to which time period she is originally from.
But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had just finished building her time machine which she named - "Dokhina Batash". She was making the final adjustments for her first trip when she noticed that a vital program was not working correctly. The program was supposed to take a number N, and find what Zephyr called its Onoroy value.
The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number 13 (11012) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr. She solved it quickly, and was on her way.
You are now given a similar task. Find the first number after N which has the same Onoroy value as N.
Input starts with an integer T (≤ 65), denoting the number of test cases.
Each case begins with an integer N (1 ≤ N ≤ 109).
For each case of input you have to print the case number and the desired result.
5
23
14232
391
7
8
Case 1: 27
Case 2: 14241
Case 3: 395
Case 4: 11
Case 5: 16
题意：给一个二进制数n，找出一个比n大的数m，要求m和n二进制下1的数目相等
首先将数转换成二进制形式，要使这个数比原数大，可以通过将低位的1和高位的0交换使值变大（当然要求相邻，想想为什么），比如10011变为10101，如果没有可以交换，就将最高位进1，第二位变为0比如1111变为10111，确定变换位置后要将变换位置后位数的0 1 换一下位置，1放在最后，比如1001110应该变为1010011，111110应该变为1001111。
#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<stack> #include<queue> #include<deque> #include<set> #include<map> #include<cmath> #include<vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; #define pi acos(-1.0) #define eps 1e-10 #define pf printf #define sf scanf #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r #define e tree[rt] #define _s second #define _f first #define all(x) (x).begin,(x).end #define mem(i,a) memset(i,a,sizeof i) #define for0(i,a) for(int (i)=0;(i)<(a);(i)++) #define for1(i,a) for(int (i)=1;(i)<=(a);(i)++) #define mi ((l+r)>>1) #define sqr(x) ((x)*(x)) const int inf=0x3f3f3f3f; int a[100],num,n,t; ll ans; bool cmp(int x,int y) { return x>y; } int main() { sf("%d",&t); for1(i,t) { num=0,ans=0; sf("%d",&n); while(n) a[num++]=n%2,n/=2; int j,tag=0; for(j=0;j<num-1;j++) if(a[j]&&!a[j+1]) { swap(a[j],a[j+1]),tag=1;//如果找到满足 0 1的，交换找到第一个，退出 break; } if(!tag)a[num-1]=0,a[num++]=1;//如果找不到交换的，最高位进1 sort(a,a+j,cmp);//将变换后的位置的1放在最后（包括加0的情况） for(int i=num-1;i>=0;i--) ans=(ans<<1)+a[i]; pf("Case %d: %lld\n",i,ans);//输出最好用long long ，防止爆int } return 0; }
