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