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 来源 topcoder 上传者骆魁永
首先打一个表：
1717 11010110101 1718 11010110110 4 0100 8 1000 7 0111 11 1011 12 01100 17 10001 555555 10000111101000100011 555557 10000111101000100101
就是从右到左找第一个是01（01是从左往右看）的位置把01换成10 再将01后面所有的1移到最右边
#include<iostream> #include<cstring> using namespace std; int main() { int n; while(cin>>n) { int a[50]; memset(a,0,sizeof(a)); // 变为二进制 int f = 0; while(n){ a[f++]=n%2; n/=2; } // 找 1 0 的位置 变为 0 1 int key = 0; for(int i = 0; i <= f; i ++) { if(a[i]==1 && a[i+1]== 0) { key = i -1; a[i]=0; a[i+1]=1; break; } } // key 之前有多少个一 int count = 0; for(int i = 0; i <= key; i ++){ if(a[i]==1) count++; } // 变为 1 for(int i = 0;i < count; i ++){ a[i]=1; } // 变为 0 for(int i = count;i <= key; i ++ ){ a[i]=0; } // 变为十进制 int h = 1; int sum = 0,i = 0; f++; while(f--){ sum+=h*a[i++]; h*=2; } cout << sum << endl; } return 0; }
#include <bitset> #include <iostream> using namespace std; int main(){ int n, i, count, j; while(cin >> n) { bitset<32> bt(n); for(i = count = 0; i < 32; ++i) { if(bt[i]) ++count; if(bt[i] && !bt[i+1]) { bt[i] = false; bt[i+1] = true; j = i; break; } } --count; for(i = 0; i < count; ++i) bt[i] = true; while(i < j) bt[i++] = false; cout << bt.to_ulong() << endl; } return 0; }
