Binary operator for binary coding training

Today I tried out the free Codility developer training service (https://app.codility.com/programmers/) and their first training task, the binary gap coding exercise ('BinaryGap').

After completing the exercise I looked around on the web to see what others came up with, and I was surprised to see most programmers converted the input number to a string, sometimes even used Math library to solve the challenge. So I didn't thought what I did was anything special, but maybe it is worth sharing after all.

The issue is about binary gaps, so let's solve it with (compute efficient) binary operators, shall we? (Spoiler alert, go do the challenge now before reading the solution below.)

using System
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        var inGap = false;
        var maxGapLenght = 0;
        var currentGapLenght = 0;
        while (N != 0)
        {
            if (inGap)
            {
                // if we reach a 1 it ends the gap
                if ((N & 1) == 1)
                {
                    inGap = false;

                    // Reset the current gap lenght to restart next gap length count from zero
                    currentGapLenght = 0;
                }
                else
                {
                    currentGapLenght++;
                    if (currentGapLenght > maxGapLenght)
                    {
                        maxGapLenght = currentGapLenght;
                    }
                }
            }
            
            // If we were not in a gap or just entered the next gap
            if (!inGap && (N & 1) == 1 && (N & 2) == 0)
            {
                inGap = true;
            }

            N = N >> 1;
        }

        return maxGapLenght;
    }
};        

This is verbatim the solution as I submitted it (30 minutes, including a 10 minutes gap chasing my daughter to get on her mandarin lesson, answering the phone and keeping an eye on my youngest). So it's not up to my usual coding style standard and includes English typos.

The crux of the approach is to do an binary logical AND operation with 1 to test the entry boundary of a gap, which must be followed by a 0 (tested by binary logical AND operation with 2 which is 10 in binary). Once we are in the gap, we can test the end of the current gap with the same test which we used to detect the entry boundary. When an end boundary is found, the gap length is reset, otherwise the gap length is increased. We keep an upper watermark on the gap length which we update upon increasing the current gap length as appropriate.

One thing we have to be careful about is that an end boundary of current gap may also be the start boundary for the next gap.

Note that for the loop end condition, we will incorrectly set 'in gap' flag to true although we are exiting. But as we are not going to enter the loop anymore, we will never increment the current gap length and will not incorrectly count a non-existing gap. i.e. it's a harmless quirk.

Couple of differences I noticed with my Codility experience as an interviewer, was that the authoring of unit tests is replaced by an input test data without validation target. I did prefer having the candidate write their own validation. I still used the input data file to test my code on increasingly difficult inputs. Also I recalled the Codility tool to have performance oriented test cases - no performance evaluation of the solution here.

Still, this is a pretty good training platform, especially coming from a service used by big tech employers in the United States. Highly recommended if you are planning to interview at Microsoft.