返回目录

题目描述

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

小船给小扇一个正整数 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

可以发现，想要找到符合要求的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 = 10001000111

因此，我们还需要将加粗子串后面的部分的'1'全部集中放到尾部。

Python算法源码

# 计算一个数的二进制表示中1的个数
def count_ones(x):
    count = 0
    while x:
        count += x & 1  # 每次判断最低位是否为1
        x >>= 1  # 将数字右移一位，相当于除以2
    return count

# 找到比给定数字x大的下一个数字y，使得y和x对应的二进制中1的个数相同
def find_next_number(x):
    ones_count = count_ones(x)  # 统计x中1的个数
    y = x + 1  # 初始y为x加1
    while count_ones(y) != ones_count:  # 当y的二进制表示中1的个数不等于x的时候
        y += 1  # 继续增加y
    return y

x = int(input())  # 从标准输入中读取整数x
result = find_next_number(x)  # 调用函数找到满足条件的y
print(result)  # 打印结果y

C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


void customLogic(int x, int y) {
    // 作示例用途
    printf("Custom logic executed with x = %d and y = %d\n", x, y);
}

// 将十进制数转换为二进制字符串
void decToBin(int num, char *s) {
    int i = 0;
    while (num > 0) {
        s[i++] = (char) (num % 2 + '0');
        num /= 2;
    }

    // 反转字符串
    int l = 0;
    int r = i - 1;
    while (l < r) {
        char tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;
        l++;
        r--;
    }
}

int main() {
    int x;
    scanf("%d", &x);

    char xBinStr[1000] = {'\0'};
    xBinStr[0] = '0';
    decToBin(x, xBinStr + 1);

    int len = (int) strlen(xBinStr);

    int countOne = 0;

    int i = len - 2; // 更改循环起始值
    while (i >= 0) {
        if (xBinStr[i] == '0' && xBinStr[i + 1] == '1') {
            // 从右向左找到了第一组"01"子串，则替换为"10"
            xBinStr[i] = '1';
            xBinStr[i + 1] = '0';

            // 如果第一组"01"子串右边存在1
            if (countOne > 0) {
                // 则将第一组"01"子串的右边部分的'1'要全部集中到尾部
                for (int j = i + 2; j < len; j++) {
                    if (j < len - countOne) {
                        xBinStr[j] = '0';
                    } else {
                        xBinStr[j] = '1';
                    }
                }
            }

            break;
        }

        // 记录第一组"01"子串右边1的个数
        if (xBinStr[i + 1] == '1') {
            countOne++;
        }
        i--; // 循环递减值
    }

    char *endptr;
    int y = strtol(xBinStr, &endptr, 2);

    printf("%d\n", y);

  
    int z = 10;

    // 调用函数
    customLogic(x, z);

    return 0;
}

Java算法源码

import java.util.Scanner;

/
class CustomClass {
  
    static void customLogic(int x, int y) {
        // 作示例用途
        System.out.println("Custom logic executed with x = " + x + " and y = " + y);
    }
}

public class Main {
    // 改写的常见逻辑，将for改为while
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt(); // 更改注释

        // 将整数x转为二进制字符串
        String xBinStr = "0" + Integer.toBinaryString(x);

        char[] yBinCharArr = xBinStr.toCharArray();

        int countOne = 0;

        int i = yBinCharArr.length - 2; // 更改循环起始值
        while (i >= 0) {
            if (yBinCharArr[i] == '0' && yBinCharArr[i + 1] == '1') {
                // 从右向左找到了第一组"01"子串，则替换为"10"
                yBinCharArr[i] = '1';
                yBinCharArr[i + 1] = '0';

                // 如果第一组"01"子串右边存在1
                if (countOne > 0) {
                    // 则将第一组"01"子串的右边部分的'1'要全部集中到尾部
                    for (int j = i + 2; j < yBinCharArr.length; j++) {
                        if (j < yBinCharArr.length - countOne) {
                            yBinCharArr[j] = '0';
                        } else {
                            yBinCharArr[j] = '1';
                        }
                    }
                }

                break;
            }

            // 记录第一组"01"子串右边1的个数
            if (yBinCharArr[i + 1] == '1') {
                countOne++;
            }
            i--; // 更改循环递减值
        }

        int m = Integer.parseInt(new String(yBinCharArr), 2);
        System.out.println(m);

  
        int z = 10;

        // 调用函数
        CustomClass.customLogic(x, z);
    }
}