给定一个正整数N,求最小的、比N大的正整数M,使得M与N的二进制表示中有相同数目的1。
举个例子,假如给定的N为78,其二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
输入若干行,每行一个数nn(1≤n≤1000000),输入"0"结束。
输出若干行对应的值。
1 2 3 4 78 0
2 4 5 8 83
算法解析
先进行进制转换,然后枚举求‘1’的个数,之后从n+1开始枚举查找第一个符合要求的数并输出
代码如下
#include<bits/stdc++.h> using namespace std; int n,m; string s; string q(int x)//进制转换 { string a; char ch; while(x>0) { ch=x%2+'0'; x/=2; a+=ch; } return a; } int f(string a)//计算‘1’的个数 { int k=0; for(int i=0;i<a.size();i++) if(a[i]=='1') k++; return k; } int main() { while(cin>>n) { if(n==0) return 0; s=q(n); m=f(s); for(int i=n+1;;i++) { string a=q(i); if(m==f(a)) { cout<<i<<endl; break; } } } return 0; }