寻找与给定正整数二进制权重相同的最小更大正整数算法

嘿，我来帮你搞定这个问题！首先明确核心需求：给定正整数N，我们要找到大于N，并且二进制表示中1的个数（也就是你说的二进制权重）完全相同的最小整数。举个例子：十进制1的二进制是1，权重为1，下一个符合条件的数是2（10）；十进制7的二进制是111，权重为3，下一个数是11（1011）。

下面我给你几种不同的实现方案，从直观到高效，一步步拆解：

方案1：直观暴力解法（易理解） #

这个思路非常直接：先算出原数的二进制权重，然后从N+1开始逐个检查每个数的二进制权重，找到第一个和原数权重相同的数就行。

手动统计权重的实现（对应你给出的代码片段补全） #

你给出的代码开头是把数字转成二进制字符数组手动统计1的个数，我帮你补全完整实现：

public static int compute(int number) {
    // 第一步：统计原数的二进制权重（1的个数）
    int count = 0;
    char[] arr = Integer.toBinaryString(number).toCharArray();
    for(int i = 0 ; i < arr.length ; ++i) {
        if(arr[i] == '1') {
            count++;
        }
    }

    // 第二步：从number+1开始找符合条件的最小数
    int nextNumber = number + 1;
    while(true) {
        int currentCount = 0;
        char[] nextArr = Integer.toBinaryString(nextNumber).toCharArray();
        for(int i = 0; i < nextArr.length; i++) {
            if(nextArr[i] == '1') {
                currentCount++;
            }
        }
        // 找到权重相同的数就返回
        if(currentCount == count) {
            break;
        }
        nextNumber++;
    }
    return nextNumber;
}

简化版（用Java内置方法） #

Java的Integer.bitCount()方法可以直接返回整数二进制中1的个数，用它可以简化代码：

public static int compute(int number) {
    int targetCount = Integer.bitCount(number);
    int nextNumber = number + 1;
    
    while (Integer.bitCount(nextNumber) != targetCount) {
        nextNumber++;
    }
    return nextNumber;
}

这种方法的优点是代码简单、容易理解，缺点是在某些极端情况（比如N是全1的二进制数，比如0b1111）下，需要循环很多次，效率偏低。

方案2：高效位运算解法（O(1)时间） #

如果要处理更大范围的整数，追求极致效率，那就用经典的位运算解法，这个方法直接通过位操作一步算出结果，不需要循环检查：

public static int compute(int number) {
    int c = number;
    // 找到最右边的1（比如c=6即0b110，rightOne=0b10）
    int rightOne = c & -c;
    // 找到比c大的、最右边的非末尾0变成1后的数（比如0b110+0b10=0b1000）
    int nextHigherOneBit = c + rightOne;
    // 得到原数和nextHigherOneBit的异或，提取出右边的1的模式
    int rightOnesPattern = c ^ nextHigherOneBit;
    // 把这些1的模式右移，去掉最右边的两个1（因为已经把一个0变成1了）
    rightOnesPattern = (rightOnesPattern / rightOne) >> 2;
    // 合并得到结果
    return nextHigherOneBit | rightOnesPattern;
}

核心逻辑拆解 #

咱们用例子来理解（比如N=6，二进制0b110，权重是2）：

1. rightOne = 6 & -6 = 0b10：找到最右边的1
2. nextHigherOneBit = 6 + 0b10 = 0b1000：把最右边的非末尾0变成1
3. rightOnesPattern = 6 ^ 0b1000 = 0b1110：提取出原数中右边的1的部分
4. rightOnesPattern = (0b1110 / 0b10) >>2 = 0b111 >>2 = 0b1：把多余的1重新排列成最小的形式
5. 最终结果：0b1000 | 0b1 = 0b1001（即十进制9），确实是大于6且权重为2的最小整数。

这种方法完全靠位运算操作，时间复杂度是O(1)，不管多大的数都能瞬间算出结果。

内容的提问来源于stack exchange，提问作者Developer