java - 查找数字中连续一位的最大数量(Java)

Question

这其实是我在HackerRank找到的一个问题.问题是要找到一个数中连续一位的最大数量。

例如:

The number 123 (0111 1011 Base 2) should output "4" (01111011)

我想找到执行此操作的最高效、最紧凑的算法。

这是我最好的尝试:

int getMaxBits(long number) {
    return number != 0 ? getMaxBits(number & (number >>> 1)) + 1 : 0;
}

这对小数字非常有用。但由于它最多可以递归调用自身 63 次，因此我认为这不是最有效的方法。

我知道迭代显然更有效，因为 Java 编译器不会在没有尾递归的情况下优化递归。我只是喜欢我可以把它写成一行。真正的问题是是否有比计算类次更有效的方法？

Answer 1

这是一种明确的实现方式，即可能有更紧凑/更高效的实现，但它至少可能更直观易懂。

count = 0
max = 0
while n > 0
    if first bit (from the right) is 1
        increment count
    else
        if count > max
            max = count
        reset count back to 0
    set n equal to itself right-shifted over 1
return max

在Java中:

static int countBits(int n) {
    int max = 0;
    int count = 0;

    while(n > 0){
        if((n & 1) == 1) count++;
        else {
            if (count > max) max = count;
            count = 0;
        }
        if (count > max) max = count;
        n = n >> 1;
    }
    return max;
}

public static void main(String[] args){
    int n = 0b1110001101111;
    System.out.println(countBits(n));
}

输出:

4