Find max amount of consecutive one-bits in number (Java)

Question

This is actually a question I found in HackerRank. The question says to find the maximum amount of consecutive one-bits in a number.

For example:

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

I would like to find the most efficient and compact algorithm that does this.

This was my best shot at it:

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

Which works great for small numbers. But since it can recursively call it self up to 63 times, I do not think this is the most efficient way to do this.

I am aware that iterating is obviously more efficient since Java compilers do not optimize recursions without tail-recursion. I just like that I can write it in one line. Real question is if there is a more efficient way than counting shifts?

If the recursive approach is not elegant enough, change it to an iterative one. — f1sh, Oct 20 '16 at 14:47
If your long is 64 bits, why is your max number of iterations not 64? — Kevin L, Oct 20 '16 at 14:48
The idea is to not use recursion - loop through the long and examine each bit with something like `if ((number & (1L << shift)) != 0)` — Kevin L, Oct 20 '16 at 14:50
You might want to look at this: [link]http://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0[/link] — Shreyas Sarvothama, Oct 20 '16 at 14:53
Shouldn't that be `number >>> 1` ? Otherwise you are sign-extending the leftmost bit. Also, can you explain the reasoning behind *and*ing the right-shifted number with `number` itself? — Klitos Kyriacou, Oct 20 '16 at 14:53
@KlitosKyriacou That is actually true, didn't try negatives. — nick zoum, Oct 20 '16 at 14:54
In C you could use `while (number &= number << 1) ++count;`, I think. — Bathsheba, Oct 20 '16 at 14:54
@KlitosKyriacou I got that snippet from [this answer](http://stackoverflow.com/a/1092421/3666763) — Kevin L, Oct 20 '16 at 14:57
FYI: Hacker's Delight, 2nd edition, section 6-3 is about this topic and contains some very interesting algorithms for this and related problems. — jacobm, Oct 20 '16 at 15:35
A sufficiently clever compiler could have converted this into the corresponding iterative form, sacrificing accurate stack traces. However, Java compilers are usually not clever at all. You will have to do the [tail call elimination](/questions/1240539/what-is-tail-recursion-elimination) yourself. (And yes, this is morally a tail call, because integer addition is monoidal.) — , Oct 20 '16 at 15:57
Before asking your question, specify what exactly you are looking for. I think you know performance difference between recursion vs iterative. So, if you are for enhanced performance with **iterative** solution, it is already on SO, just try to google. (i.e. [the link](http://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0)). Otherwise, if you are for enhanced performance with **recursion** solution, it has been already answered. Go and investigate. — Soner from The Ottoman Empire, Oct 20 '16 at 20:16
@snr I know that recursion is not as efficient as iteration due to tailing, I only use it because with recursion I can write it one line. What I am really asking is if there is a more efficient way than counting shifts. — nick zoum, Oct 21 '16 at 07:00

Soner from The Ottoman Empire · Answer 1 · 2016-10-20T20:21:28.307

2

You can convert your recursion into tail-recursion to get enhanced performance. It works thriftier for stack usage. If you are not aware of meaning of tail-recursion just read the prior link.

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);
    }
}

Try it for -1 (long), which is 0xFFFFFFFF then compare the tail version with your version

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

edited Oct 20 '16 at 20:21

answered Oct 20 '16 at 15:15

Soner from The Ottoman Empire

18,731
3
79
101

Not now. There is much performance difference(i.e. -1(long)) btw yours and mine. @nickzoum – Soner from The Ottoman Empire Oct 20 '16 at 16:00
while giving downvote, specify the reason, don't behave like a tomfool, am I looking like a newbie on SO? – Soner from The Ottoman Empire Oct 20 '16 at 20:10
(No down-vote (yet:), but: How does this answer `[is there] a more efficient way than counting shifts?`) – greybeard Oct 21 '16 at 19:41
the editing of the question was made by me yesterday. Track days of the question – Soner from The Ottoman Empire Oct 22 '16 at 10:42
(The addition of `Real question is if there is a more efficient way than counting shifts?` was by nick zoum.) – greybeard Oct 22 '16 at 12:19

score 2 · Answer 2 · answered Oct 20 '16 at 19:51

Here's an explicit way of doing it i.e. there probably is a more compact/efficient implementation but it may at least be more intuitive to understand.

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

in 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));
}

Output:

4

(How does this answer `[is there] a more efficient way than counting shifts?` (approach in the question: # in the longest run, _not_ ld(n)(_position of most significant bit_) like this answer)) — greybeard, Oct 21 '16 at 19:48
My basic assumption, going with some of the suggestions in the comments, was, in general, an iterative solution is more efficient than a recursive one since in recursion you have to remember the previous function inputs etc. whereas this isn't the case with iteration. So my answer, since it is iterative, in comparison to the OP's, which is recursive, is presumably "more efficient" — Bobas_Pett, Oct 21 '16 at 20:31

Sergey Morozov · Accepted Answer · 2016-10-21T08:42:01.420

    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);

So I have prepared JMH benchmark:

@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);
    }
}

There are results here:

# 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

On the face of it my solution is lose, but if you have really big bit-array, size of which more than size of long?

p.s. - any concern on code are welcome.

score 0 · Answer 4 · edited May 23 '17 at 12:33

0

As described by Shawn Chin in this answer, here's a port of this to 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);
  }

edited May 23 '17 at 12:33

Community

1
1

answered Oct 20 '16 at 14:55

Shreyas Sarvothama

486
2
10

2

Does this compile in Java? – Bathsheba Oct 20 '16 at 14:56
You should just comment it (link)/ mark as duplicate then – Treycos Oct 20 '16 at 14:57
@Bathsheba will not because of the `while(in)` – nick zoum Oct 20 '16 at 14:57
@Bathsheba no, because it is converting Boolean to long – nick zoum Oct 20 '16 at 14:59
For the reason that i've given – Treycos Oct 20 '16 at 15:00
@Treycos I would not consider this a duplicate since the other question was for C, this is for Java – nick zoum Oct 20 '16 at 15:01
Also this would not really work for negatives, would it? – nick zoum Oct 20 '16 at 15:02
@nickzoum Thanks for noticing, it doesnt.. will change it – Shreyas Sarvothama Oct 20 '16 at 15:04
@KevinL it does count consecutive bits of one, not just set bit – Shreyas Sarvothama Oct 20 '16 at 15:08
@KevinL input should be an integer – Shreyas Sarvothama Oct 20 '16 at 15:10
@KevinL answer is 4 – Shreyas Sarvothama Oct 20 '16 at 15:12
This will pretty much have the same efficiency as my method. So is bit shifting 1 - 64 times the best way to do this? – nick zoum Oct 20 '16 at 15:14
it doesnt have the overhead of recursive call stack – Kevin L Oct 20 '16 at 15:18
@KevinL hence the pretty much – nick zoum Oct 20 '16 at 16:31
Shouldn't it say `while (in != 0)` so that it works for negative numbers? – Klitos Kyriacou Oct 20 '16 at 20:33

Find max amount of consecutive one-bits in number (Java)

4 Answers4