华为OD统一考试 - 找数字

题目描述

小扇和小船今天又玩起来了数字游戏，

小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：

4对应二进制100

8对应二进制1000

其中1的个数都为1个

现在求 m 的最小值。

输入描述

输入一个正整数 n（1 ≤ n ≤ 1e9）

输出描述

输出一个正整数 m

用例

题目解析

我们可以举几个例子来说明此题的解法：

n： 10010100

m：10011000

n： 11101001

m：11101010

n： 11100010

m：11100100

可以发现，想要找到符合要求的m，其实只需要将 n 二进制串中从右往左找到的第一组 "01" 子串 变为 "10" 即可。

这样就能在不新增二进制'1'的情况下，且差距最小的情况下，找到比n大的最小的m的二进制串

那么对于：

n = 111111

n = 10000

这种找不到 "01" 子串的情况，该怎么处理呢？

很简单，给n的二进制串最前面拼接一个0即可，即上面两个n的二进制串变为

n = 0111111  => m = 1011111 

n = 010000  => m = 100000

此时前面方法依旧适用。

但是上面方法依旧是存在问题的，什么问题，因为我们将"01"变为"10"的过程中实际上对于该子串后面的部分也会产生影响。

比如

n =  10000111100

如果我们将 01 子串变为 10，则m的二进制串为

m = 10001011100

此时m虽然比n大，但是并不是最小的m，此时由于红色部分发生了进位操作，因此红色部分后面的子串还有变小的可能，比如更优的m二进制串应该为：

m = 1