2021 年 9 月青少年软编等考 C 语言五级真题解析

T1. 问题求解

给定一个正整数 $N$ ，求最小的 $M$ 满足比 $N$ 大且 $M$ 与 $N$ 的二进制表示中有相同数目的 $1$ 。

举个例子，假如给定 $N$ 为 $78$ ，二进制表示为 $100\ 1110$ ，包含 $4$ 个 $1$ ，那么最小的比 $N$ 大的并且二进制表示中只包含 $4$ 个 $1$ 的数是 $83$ ，其二进制是 $101\ 0011$ ，因此 $83$ 就是答案。

时间限制：1 s
内存限制：64 MB

输入
输入若干行，每行一个数 $N\ (1 ≤ N ≤ 10^6)$ ，如果这行为 $0$ 表示输入结束。
输出
对于每个 $N$ ，输出对应的 $M$ 。
样例输入
```
1
2
3
4
78
0
```
样例输出
```
2
4
5
8
83
```

思路分析

此题考查枚举算法与数位分离，属于入门题。

首先计算出 $n$ 的二进制形式中 $1$ 的个数。然后从 $n + 1$ 开始依次枚举，寻找与 $n$ 的二进制形式中 $1$ 的个数相等的第一个数字即可。

/*
 * Name: T1_1.cpp
 * Problem: 问题求解
 * Author: Teacher Gao.
 * Date&Time: 2025/01/08 23:50
 */

#include <iostream>

using namespace std;

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n && n) {
   
        int p = n, cnt = 0;
        while (p) {
   
            p &= p - 1;
            cnt++;
        }
        while (1) {
   
            p = ++n;
            int cnt2 = 0;
            while (p) {
   
                p &= p - 1;
                cnt2++;
            }
            if (cnt2 == cnt) {
   
                cout << n << "\n";
                break;
            }
        }
    }

    return 0;
}

从二进制的角度考虑，要保证比 $n$ 大，且二进制形式中 $1$ 的数量不变，相当于让某一个 $1$ 向左移动一位。容易想到向左移动的这个 $1$ 的左边必须是 $0$ ，那么我们可以从最低位 $1$ 开始向左寻找，当发现某一位是 $0$ 的时候，将它右边那个 $1$ 移动过来即可。但是这样仍然不是最小的，我们需要将这一位右边的 $1$ 全都移动到最低位才能满足最小。观察示例中 $78$ 和 $83$ 的二进制形式，可以更好地理解这一点。