Найти максимальное количество последовательных одноразрядных чисел (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); 

Так я подготовил JMH тест:

@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