java - 查找大于给定数字且与给定整数具有相同二进制权重的最小 +ve 整数的算法

Question

正整数的二进制权重是其二进制表示中 1 的个数。例如，十进制数1的二进制权重为1，十进制数7(二进制为111)的二进制权重为3。

给定一个正整数N，找到大于N且与N具有相同二进制权重的最小整数。

public static int compute(int number)   {
    int  count = 0, nextNumber;
    char[] arr =  Integer.toBinaryString(number).toCharArray();
    for(int i =0 ; i < arr.length ;++i) {
        if(arr[i] == '1')
            ++count;
    }
    nextNumber = findNextNumber(number,count);
    return nextNumber;
}
public static int findNextNumber(int number, int weight) {
    char[] arr;
    boolean flag = true;
    int count;
    while (flag) {
        // increment number and convert it into char array
        arr = Integer.toBinaryString(++number).toCharArray();
        count = 0;
        for(int i =0 ; i < arr.length; ++i) {
            if(arr[i] == '1')
                ++count;
        }
        if(count == weight) {
            flag = false;
        }
    }

    return number;
}

我的解决方案工作正常，但它的复杂性似乎是 O(NlogN)。这可以通过其他方法在 O(N) 或 O(log N) 中实现吗？

Answer 1

这种操作有时被称为“snoob”。这是一个bunch of approaches from the Hacker's Delight book .可能最好的方法是使用 Integer.numberOfTrailingZeros ，它可能会编译成硬件指令(未经测试):

int snoob1(int x) {
   int smallest, ripple, ones;  // x = xxx0 1111 0000
   smallest = x & -x;           //     0000 0001 0000
   ripple = x + smallest;       //     xxx1 0000 0000
   ones = x ^ ripple;           //     0001 1111 0000
   ones = ones >>> (2 + Integer.numberOfTrailingZeros(x)); //     0000 0000 0111
   return ripple | ones;        //     xxx1 0000 0111
}

(“2+”部分也可能存在溢出问题，因为在 Java 中移位计数是模 32)