求最小的比 n 大、且二进制中 1 的个数与 n 相同的数：对最低位 1 做一次 Gosper 进位，再把被清空的 1 补回最低位，单次 O(1)。
OJ: roj
题目 ID: 1223
难度:普及-
标签:位运算贪心python
创建: 2026-09-30 00:29
更新: 2026-10-05 05:57
题目描述
给定一个正整数 1。
例如 1，满足条件的最小数是
输入若干行，每行一个数 0 结束。对每个
样例：输入 1 / 2 / 3 / 4 / 78 / 0，对应输出 2 / 4 / 5 / 8 / 83。
思路
把 1 整体进位一格（low = n & -n，carried = n + low），就完成了"变大"且 popcount 少了若干个 1；再把被清空的 1 补回最低位即可最小。被改动位为 n ^ carried，右移两位丢掉新产生的 1，再除以 low 折算到最低位，得到要补回的 1 串，按位或回去即为答案，单次询问
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:29
# update_at: 2026-09-30 00:29
import sys
from itertools import takewhile
def next_same_ones(n: int) -> int:
"""返回大于 n 的最小整数，其二进制表示中 1 的个数与 n 相同（Gosper 进位法）。"""
low = n & -n # n 最低位置 1 的值 2^l，即进位的入口
carried = n + low # 从第 l 位起的连续 1 全部进位清空，其上方第一个 0 变 1
return carried | ((n ^ carried) >> 2) // low # 把被清空的 k 个 1 中的 k-1 个铺回最低位
def solve() -> None:
data = map(int, sys.stdin.buffer.read().split())
out = [str(next_same_ones(n)) for n in takewhile(bool, data)] # 读到 0（假值）即结束
sys.stdout.write('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 05:57
* update_at: 2026-10-05 05:57
*/
#include <bits/stdc++.h>
typedef long long ll;
// 求比 n 大、且二进制中 1 的个数与 n 相同的最小数（Gosper 进位）
ll next_same_ones(ll n) {
ll low = n & -n; // 最低位的 1，即 2^l
ll carried = n + low; // 最低位加 1 引发连锁进位：连续 1 段清空，上方第一个 0 位变 1
// n ^ carried 的置 1 位是被改动的位；>> 2 丢掉新产生的那位，// low 把剩下的 1 折算到最低位
return carried | (((n ^ carried) >> 2) / low);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
ll n;
while (std::cin >> n && n != 0) { // 输入以 0 结束
std::cout << next_same_ones(n) << "\n";
}
return 0;
}