Calculating the 'binary gap' of a number

Question

Inspired by this question and therefore this one I decided that clearly the best most readable way to solve this is with Regular Expressions.

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.

I decided to remove the limit of positive numbers only.

Here's the code:

public static int ComputeLargestBinaryGap(int value)
{
    var regexp = new Regex("(?<=1)(0+)(?=1)");
    var valueAsBinary = Convert.ToString(value, 2);
    return 
        regexp.Matches(valueAsBinary)
            .Cast<Match>()
            .Select(m => m.Value)
            .DefaultIfEmpty(string.Empty)
            .Max(s => s.Length);
}

You'll notice that this can be trivially extended to also work for long or any number representation you can convert to a string binary representation.

I appreciate that's a pretty small amount of code to review but would be intrigued as to whether there's anything I could improve.

For the record, my first actual solution was bit shifting an unsigned int but I stand by the Regular Expression solution.

Answer 1

I think using Regex will be too much for this little task. A simple split by 1s should suffice.

public static int ComputeLargestBinaryGap2(int value)
{
    return Convert
            // convert to binary
            .ToString(value, 2)
            // remove leading and trailing 0s, as per requirement
            .Trim('0')
            // split the string by 1s
            .Split(new [] { '1' })
            // find the length of longest segment
            .Max(x => x.Length);
}

We can also solve the problem from a mathematical approach, with logical operators and bit-shiftings :

public static int ComputeLargestBinaryGap3(int value)
{
    // casting it to uint while keeping the same binary value, like reinterpret_cast<unsigned int>
    //var unsigned = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);
    var unsigned = unchecked((uint)value);
    // flag used to ignore counting trailing 0's
    var pastTrailing0 = false;

    int max = 0, count = 0;
    while(unsigned > 0)
    {
        if ((unsigned & 1) == 1)
        {
            if (count > max)
                max = count;

            count = 0;
            pastTrailing0 = true;
        }
        else if (pastTrailing0)
        {
            count++;
        }

        unsigned = unsigned >> 1;
    }

    return max;
}

---

EDIT: After this answer was posted, OP updated on his definition of "best", which leans toward readability. I'll add my comments on his code here :

1. There is no benefit in declaring the variable, regexp , for the regular express, without giving a meaningful name to it, other than stating the obvious. It should be renamed to binaryGap.

2. valueAsBinary is a quite misleading name. One would think it the value stored in the binary format, which is pretty much how every number is stored... However, it stores the binary string of value. Therefore, it should be renamed to binaryString, or valueAsBinaryString.

3. The Match class already have a Length property that could be used instead of the long way match.Value.Length. This property is cached, so we are not re-measuring the length of the string, as you can see here.

And, here is the final result :

public static int ComputeLargestBinaryGap(int value)
{
    var binaryGap = new Regex("(?<=1)(0+)(?=1)");
    var binaryString = Convert.ToString(value, 2);
    return 
        binaryGap.Matches(binaryString)
            .Cast<Match>()
            .Select(m => m.Length)
            .DefaultIfEmpty(0)
            .Max();
}

Answer 2

Another bit shifting solution that is a bit more general than @Xiaoy312's. It does not use a type cast and can therefore be implemented as generic function. Also, the trailing zero handling is simpler.

public static int ComputeLargestBinaryGap(int n)
{
    int max = 0, count = 0;
    n |= n - 1;
    while (n != n >> 1)
    {
        n >>= 1;
        if ((n & 1) == 1)
        {
            if (count > max)
                max = count;
            count = 0;
        }
        else
            count++;
    }
    return max;
}

Some details:

• n |= n - 1; replaces all trailing zeros with ones.

• n != n >> 1 works for both positive and negative numbers.

• n >>= 1; must be moved upwards to not terminate one iteration early for negative inputs. It can be moved because the least significant bit is a one or ignored zero anyway.

Answer 3

You could use the BitArray class to simplify binary operations:

private static int ComputeLargestBinaryGap(int x)
{
    BitArray ba = new BitArray(new[] { x });

    int maxCount = 0;
    int startGapIndex = -1;

    for (int i = 0; i < ba.Length; i++)
    {
        if (!ba[i])
            continue;

        if (startGapIndex != -1)
        {
            int count = i - startGapIndex - 1;
            if (count > maxCount)
            {
                maxCount = count;
            }
        }
        startGapIndex = i;
    }
    return maxCount;
}