题目描述
The binary weight of a positive integer is the number of 1's in its binary representation.for example,the decmial number 1 has a binary weight of 1,and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.Give a positive integer N,return the smallest integer greater than N that has the same binary weight as N.N will be between 1 and 1000000000,inclusive,the result is guaranteed to fit in a signed 32-bit interget.
输入
The input has multicases and each case contains a integer N.
输出
For each case,output the smallest integer greater than N that has the same binary weight as N.
样例输入
1717
4
7
12
555555
样例输出
1718 8 11 17 555557
题解：
1717（0110 1011 0101），下一位是 1718（0110 1011 0110）
767（0010 1111 1111），下一位是 895（0011 0111 1111）
348（0001 0101 1100），下一位是 355（0001 0110 0011）
其中不难发现一个规律，从右起的第一个“01”改变为“10”，并且在“01”的后面所有的“1”都移动至最后，事实上，这个就是解题的关键点，那么整个问题求解的核心就转移到这两个子问题：
1. 将右起第一个“01”，改变为“10”
2. 将该“01”后面的所有“1”移动至最后
1 #include <cstdlib> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cmath> 6 #include <iostream> 7 #include <vector> 8 #include<string> 9 #include<cstring> 10 #include<string.h> 11 #include<set> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 using namespace std; 16 typedef long long LL; 17 18 int main() 19 { 20 int n; 21 while(cin>>n) 22 { 23 int b=n&(-n);// 得到n中最后一个‘1’到最后的值 24 int t=n+b; // 产生进位， 实现‘01’ 变成 ‘10’ 25 int s=t^n; // 得到进位中发生变动的位 26 int k=(s>>2)/b;//先 ‘01’->'10'发生后不要去改变这两位，所以右移2位，然后将‘01’以后的‘1’移动到最后。 27 int n=t|k; // 最后的结果就是t|k 28 cout<<n<<endl; 29 } 30 return 0; 31 }