题目描述

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

• 4对应二进制100
• 8对应二进制1000
• 其中1的个数都为1个

现在求 m 的最小值。

输入描述

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

输出描述

输出一个正整数 m

用例

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = findNextNumberWithSameNumberOfOnes(n);
        System.out.println(m);
        scanner.close();
    }

    private static int findNextNumberWithSameNumberOfOnes(int n) {
        // c0 表示在找到的 "01" 模式中 0 的个数