找到最大數量的連續1位數（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

BitSet bitSet = BitSet.valueOf(new long[] {123}); 
    int count = 0; 
    int max = 0; 
    for (int i=0; i < bitSet.size(); i++) { 
     if(bitSet.get(i)) { 
      count++; 
     } else { 
      max = Math.max(max, count); 
      count = 0; 
     } 
    } 
    System.out.println(max); 

所以我準備了江鈴控股基準：

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
@Warmup(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS) 
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) 
@Fork(1) 
@State(Scope.Benchmark) 
public class MyBenchmark { 

    @Param({"0", "1", "255", "4294967295", "-1"}) 
    public long value; 

    @Benchmark 
    public int testBitSet() { 
     int count = 0; 
     int max = 0; 
     BitSet bitSet = BitSet.valueOf(new long[]{value}); 
     for (int i = 0; i < bitSet.size(); i++) { 
      if (bitSet.get(i)) { 
       count++; 
      } else { 
       max = Math.max(max, count); 
       count = 0; 
      } 
     } 
     return max; 
    } 

    @Benchmark 
    public int testBitWiseOperation() { 
     int max = 0; 
     int count = 0; 
     while (value > 0) { 
      if ((value & 1) == 1) count++; 
      else { 
       if (count > max) max = count; 
       count = 0; 
      } 
      if (count > max) max = count; 
      value = value >> 1; 
     } 
     return max; 
    } 

    @Benchmark 
    public int testRecursion() { 
     return getMaxBits(value); 
    } 
    public static int getMaxBits(long number) { 
     return accGetMaxBits(number, 0); 
    } 

    private static int accGetMaxBits(long number, int accum) { 
     if (number == 0) return accum; 
     accum += 1; 
     return accGetMaxBits(number & (number >>> 1), accum); 
    } 
} 

這裏有結果：

# Run complete. Total time: 00:03:49 

Benchmark       (value) Mode Cnt Score Error Units 
MyBenchmark.testBitSet      0 avgt 5 3,570 ? 0,019 ns/op 
MyBenchmark.testBitSet      1 avgt 5 84,515 ? 2,188 ns/op 
MyBenchmark.testBitSet     255 avgt 5 85,238 ? 0,581 ns/op 
MyBenchmark.testBitSet   4294967295 avgt 5 80,629 ? 0,816 ns/op 
MyBenchmark.testBitSet     -1 avgt 5 66,905 ? 1,446 ns/op 
MyBenchmark.testBitWiseOperation   0 avgt 5 2,200 ? 0,297 ns/op 
MyBenchmark.testBitWiseOperation   1 avgt 5 2,164 ? 0,011 ns/op 
MyBenchmark.testBitWiseOperation   255 avgt 5 2,166 ? 0,030 ns/op 
MyBenchmark.testBitWiseOperation 4294967295 avgt 5 2,172 ? 0,047 ns/op 
MyBenchmark.testBitWiseOperation   -1 avgt 5 2,164 ? 0,028 ns/op 
MyBenchmark.testRecursion     0 avgt 5 2,171 ? 0,015 ns/op 
MyBenchmark.testRecursion     1 avgt 5 2,460 ? 0,029 ns/op 
MyBenchmark.testRecursion    255 avgt 5 9,546 ? 0,090 ns/op 
MyBenchmark.testRecursion   4294967295 avgt 5 31,357 ? 0,389 ns/op 
MyBenchmark.testRecursion     -1 avgt 5 66,708 ? 0,349 ns/op 

在表面上看我的解決方案是輸了，但如果你有真正的大位陣列，其尺寸比的長條狀的多嗎？

p.s. - 歡迎任何關於代碼的問題。

Answer 2

正如肖恩·奇在this answer描述，這裏的這個端口到Java：

public static void count_consecutive_ones(int in) { 
     int count = 0; 
     while (in>0) { 
      in = (in & (in << 1)); 
      count++; 
     } 
     System.out.println(count); 
    } 

    public static void main(String[] args) { 
     count_consecutive_ones(15); 
    } 

Answer 3

您可以將遞歸轉化爲tail-recursion來獲得更高的性能。它對棧的使用起到了節約的作用。如果您不知道尾遞歸的含義，請閱讀前面的鏈接。

public class ConsecutiveOnes 
{ 
    public static void main(String[] args) 
    { 
     long num = 123; 
     System.out.println(num + " has " + getMaxBits(num) + " consecutive 1's"); 

    } 

    public static int GetMaxBits(long number) 
    { 
     return accGetMaxBits(number, 0); 
    } 

    private static int accGetMaxBits(long number, int accum) 
    { 
     if(number == 0) return accum; 
     accum += 1; 
     return accGetMaxBits(number & (number >>> 1), accum); 
    } 
} 

嘗試它-1（長），這是0xFFFFFFFF然後用你的版本比較尾巴版本

long num = 0xFFFFFFFF; 
System.out.println(num + " has " + accGetMaxBits(num) + " consecutive 1's"); 
// Out: -1 has 64 consecutive 1's 

Answer 4

這裏做即有可能是一個更緊湊/高效實現的明確方式但它至少可以更直觀地理解。

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