10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm fairly confident that using a loop to just walk through it will be faster than your solution (firing up the regex, casting + selecting everything and another traversal to find the maximum). When you say "the best way" what do you mean exactly? In terms of readability, execution time, memory impact, etc? \$\endgroup\$ – Jeroen Vannevel May 11 '16 at 15:37
  • \$\begingroup\$ @JeroenVannevel By 'best' I meant readability. I know it will be hideously slow compared to simple string manipulation or bit shifting. \$\endgroup\$ – RobH May 11 '16 at 17:37
  • 1
    \$\begingroup\$ You prefer regexp because of.... Readability? Right. \$\endgroup\$ – Mattias Åslund May 11 '16 at 17:53
  • 1
    \$\begingroup\$ @MattiasÅslund It almost sounded like a joke, but Regex is probably the most simplistic solution here. At least, compared my to arcane scripting. \$\endgroup\$ – Xiaoy312 May 11 '16 at 18:19
  • \$\begingroup\$ @MattiasÅslund - there's no need to be snide. I genuinely find simple regular expressions easy to read! The one in my question is fewer than 20 characters. Yes they can be abused, but don't think they're never useful because of that. \$\endgroup\$ – RobH May 11 '16 at 18:40
14
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ Your second solution (barring 2 variable names) is almost identical to my other solution and I mean scarily similar. I was optimising for readability not running time. \$\endgroup\$ – RobH May 11 '16 at 17:39
  • 1
    \$\begingroup\$ @RobH I guess we could say great minds think alike, haha. \$\endgroup\$ – Xiaoy312 May 11 '16 at 18:22
  • \$\begingroup\$ @RobH I updated answer with a review of your code. \$\endgroup\$ – Xiaoy312 May 11 '16 at 18:49
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Neat! I love the hack you did to removed the trailing 0s. \$\endgroup\$ – Xiaoy312 May 11 '16 at 18:53
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Sep 25 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.