Find longest sequence of zeroes in a binary representation of an integer

Question

I am aware this problem has been asked before but in java e.g Printing longest sequence of zeroes. This is a similar problem but in C#. A brief explanation of the problem is to find the longest sequence of zeroes in a binary representation of an Integer. For instance, the Integer 529 in binary gives 1000010001 and the longest sequence of zeroes is 4. So far I have achieved this using the following code

using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static int Solution(int N)
    {
        List<int> occurenceCount = new List<int>();
        int Counter=0,value;

        if(N == 0)
        {
            Console.WriteLine(0);
            return 0;
        }

        else{
            string binaryRep = Convert.ToString(N,2);

            // find the first occurence of 1 
            int FirstIndex = binaryRep.IndexOf("1");

            // find the last occurence of 1
            int LastIndex = binaryRep.LastIndexOf("1");

            for(int i = FirstIndex; i<LastIndex+1;)
            {

                value = i;

                while(binaryRep[value++] != '1' )
                {
                  Counter = Counter+1;
                }
                occurenceCount.Add(Counter);
                i= value;
               Counter=0;
            }
        return occurenceCount.Max();
        }
    }
    static void Main()
    {
       Console.WriteLine(Solution(1041));
    }
}

Brief description of the code: If the Integer passed is 0, then 0 is returned else the longest sequence. The convert.ToString() gives the binary representation. To improve the performance, I keep track of the index of the first 1 and the last index of 1 and use this in the for loop. In the while loop, once a 0 is encountered in between two 1's then a counter is incremented until a 1 is encountered and later on added to the List. I would appreciate if any one can tell me how to improve on this.

Answer 1

Unless performance is somehow critical, you'd do far better by just making use of String.Split on '1' after getting a binary representation. Then you can search for the longest string in that array. The current implementation is very low level and hard to easily understand.

A programmer who sees the code as it is now would have to invest time to understand how it works, whereas relying on (even if slower) a few library calls can make an algorithm easier to understand for programmers, thus being of more value than the faster, low level algorithm. It's also faster to write such things and less likely to contain bugs because most of the actual work is done by the standard libraries, which are thoroughly tested by other programmers.

Answer 2

What about:

var value = 529;
var count = 0;
var countMax = 0;
while(value > 0)
{
    count = value % 2 == 0 ? count + 1 : 0;
    value /= 2;
    countMax = Math.Max(count, countMax);
}
// result in: countMax;

[Edit: Version that supports also negative ints]

var value = 529;
var count = 0;
var countMax = 0;
var factor = value < 0 ? -1 : 1;
while((value * factor) > 0)
{
    count = value % 2 == 0 ? count + 1 : 0;
    value /= 2;
    countMax = Math.Max(count, countMax);
}
// result in: countMax;

[Edit2: added explanation]

Converting the integer to a string of bits and count the linked zeros using string operations is one option. However, it needs lots of code and is not really performant.

Another option is to check if the number is even. If so, the last bit is not set ('0'). Dividing the number with 2 removes the last bit, so that we can check the next bit... and so on.

Answer 3

Stylistically there is room for improvement. With C# you are encouraged to use meaningful names. Also parameters and variables should begin with a lowercase. That would change this:

public static int Solution(int N)

To

public static int Solution(int number)

While your use of braces is decent, you have a mixup of spacing. Let your code "breath" by having spaces around things, but don't have a white line before an else. That would change this:

if(N == 0)
{
    Console.WriteLine(0);
    return 0;
}

else{

To this:

if (N == 0)
{
    Console.WriteLine(0);
    return 0;
}
else
{

Each variable declaration should be on its own line. This changes this:

int Counter=0,value;

To

int counter = 0;
int value;

Your methods should be singular in purpose. In your OP, Solution finds the solution and also writes to the console. It really should be just to find the solution, and let Main take care of the display.

And it could be much smaller. Taking @Pimgd 's suggestion, the code could be reduced to:

public static int Solution(int number)
{
    if (number == 0)
    {
        return 0;
    }
    return Convert.ToString(number, 2).Split(new char[] { '1' }).Max(x => x.Length);
}

Or even this one-liner:

public static int Solution(int number) => number == 0 ? 0 : Convert.ToString(number, 2).Split(new char[] { '1' }).Max(x => x.Length);

Though as a one-liner it looks a bit jumbled. The guiding rule of thumb is to use the code that is easiest to read by another developer.

Answer 4

Others have already provided alternative solutions. I'll provide a small review of your original code instead:

Names

Solution is not a descriptive name. Renaming that method to something like MaxConsecutiveZeroBits will make its purpose more clear.

Some of your variables start with a capital letter, others do not. Normally CamelCase is used for type and method names, whereas camelCase is used for parameters and local variables. Being consistent makes your code easier to read.

Variable declaration

In C# there's no need to declare variables at the start of a method. I'd declare them in the smallest possible scope, just before they are actually used. This takes less skipping around, which makes the code easier to read.

Improvements

You don't need to keep a list of counts. You only need to keep track of the maximum count so far. After counting a sequence of zeroes, compare it against the current maximum count. If it's bigger, store it. Otherwise, discard it.

With the above change, you don't need to check up to LastIndex + 1 to prevent the list from staying empty, so that + 1 can be left out. Also, you can start at FirstIndex + 1, because the character at FirstIndex is certainly a 1.

Other changes

Counter = Counter + 1 can be rewritten as Counter += 1, or Counter++.

The value variable serves no useful purpose. You can just use i directly instead.

I'd remove that Console.WriteLine call from Solution. It's useful during development, but also ties your code to requiring a console, and causes it to have unexpected side-effects.

The if (N == 0) block immediately returns, so the rest of the code doesn't really need to be put in an else block. Not much of a problem here, but not using else blocks in methods that have multiple 'early-out' checks can prevent a lot of nesting, improving readability.

Answer 5

Bug

What none of the four existing answers have pointed out is that your code has a bug. Solution(8) should give 3 but actually gives 0. The problem is that looping only until the last '1' fails to take into account the possibility that the longest run of zeros is after the last '1'.

Priorities

There's often a tradeoff between performance and readability. It's extremely unlikely that this method is going to be a major bottleneck, so Pimgd's solution in two lines which values readability above all else is likely to be the best option. But if you (and your team, if relevant) are willing to sacrifice readability for performance, bit-bashing will be faster than converting to a string and then processing the string. But there are still readability/performance tradeoffs within bit-bashing. There's the simple linear approach proposed by JNS, which can be simplified to

    public static int LongestZeroRun(int n)
    {
        int longest = 0, current = 0;
        while (n != n >> 1)
        {
            current = ((n & 1) == 0) ? current + 1 : 0;
            if (current > longest) longest = current;
            n = n >> 1;
        }
        return longest;
    }

and correctly handle negative inputs.

But for really extreme cases, it's possible to process multiple bits at once. E.g.

    private static readonly int[] DeBruijn = new int[]
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    public static int CountTrailingZeroes(int n)
    {
        return DeBruijn[(((n & -n) * 0x077cb531) >> 27) & 31];
    }

    public static int LongestZeroRun(int n)
    {
        int longest = 0;
        while (n != n >> 1)
        {
            int current = CountTrailingZeroes(n);
            if (current > longest) longest = current;
            n >>= current;
            n >>= CountTrailingZeroes(~n);
        }
        return longest;
    }

Answer 6

I'm not at my programming machine now so I can't write and test code. But here's a sketch of a shift differential approach.

1. Shifted xor gives 1 at all positions of transition either 0 to 1 or 1 to 0 ( compare to a [1 -1] digital filter running over the bits ):

   (x<<1)^x
   

2. One variable stores first zero and one first one (anding with bitwise inversion)

3. Sequence of ffs ( find first set ) which is a hardware operation in most modern CPUs. Largest difference of consecutive positions will be the number we want. Stop when both numbers are zero.

---

PRO Good performance for numbers with many consecutive ones and zeros.

CON This will likely be bad for numbers with many toggles between 0 and 1.

BUT We can do a population count (popcnt - often also in hardware) on numbers in 2) to count the number of fields of 0s and 1s and then decide wether to use this method or some other.

---

EDIT Oh no this was for C#, I was going all performance geeky here with C and C++ considerations and even lower stuff. Maybe I can delete it if you find it too off topic.