2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)
题目描述
小扇和小船今天又玩起来了数字游戏，
小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：
- 4对应二进制100
- 8对应二进制1000
- 其中1的个数都为1个
现在求 m 的最小值。
输入描述
输入一个正整数 n（1 ≤ n ≤ 1e9）
输出描述
输出一个正整数 m
用例1
输入
2
输出
4
说明
2的二进制10，
4的二进制位100，
1的个数相同，且4是满足条件的最小数
用例2
输入
7
输出
11
说明
7的二进制111，
11的二进制位1011，
1的个数相同，且11是满足条件的最小数
用例3
输入
6
输出
9
说明
6的二进制0110，
9的二进制位1001，
1的个数相同，且11是满足条件的最小数
解题思路
本题可以通过把十进制数转化成二进制，然后移动1的位置来得到1个数不变，但更小的数。比如：
1000001
1000010
11101
11110
即只需要把最右边开始查到的第一对01变为10即可。
如果没有01的情况如何处理，比如1000，1111，只需要前面加个0，依然可以用前面的方法解答，
01000
10000
01111
10111
但还有一些特殊情况，上述方法不能解决，比如1001111000
1001111000
1010111000 //按照上述方法的答案
1010000111 //实际的正确答案
即01右边存在1时，需要把1全移到最右边。
考点
逻辑分析
代码
c++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,ans=0;
cin>>n;
string str;
while(n>0) {
int res=n%2;
str=to_string(res)+str;
n=n/2;
}
str="0"+str; //十进制转成二进制字符串
int onecnt=0; // 记录01右边1的个数
