茂名模板建站代理国家培训网官网

T1. 问题求解

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

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

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

• 输入
  输入若干行，每行一个数 $N(1\le N\le 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$ 的二进制形式，可以更好地理解这一点。

最优策略既然已经分析出来了，那么只要找到那个合适的 $1$，答案便是固定的。首先通过 n & -n 可以求出 $n$ 的最低位 $1$ 的位权，从这一位开始向左寻找第一位 $0$，同时统计 1 1