题目描述:
小扇和小船今天又玩起来了数字游戏,小船给小扇一个正整数n (1<=n<=1e9),小扇需要找到一个比n大的数字m,使得m和n对应的二进制中1的个数要相同(如4对应二进制100,8对应二进制1000,1的个数都为1),现在求m的最小值。
输入描述:
输入:第一行输入一个正整数n(1<=n<=1e9)。
输出描述:
输出:输出一个正整数m。
示例1
输入:
2
输出:4
说明:2的二进制10,4的二进制位100,1的个数相同,且4是满足条件的最小数
示例2
输入:
7
输出:11
说明:7的二进制111,11的二进制位1011,1的个数相同,且11是满足条件的最小数
解题思路:找到第一个出现的"01"(即一个0跟着一个1)并将其转换为"10"。这种转换会使整数稍微变大,但会保持二进制中1的数量不变。为了使得得到的数尽可能小,在做了上述转换后,需要将所有的1尽可能地移动到最右边(即低位