Find largest binary gap of a number N I have picked up a problem from Codility website and tried to work it out.

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.

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

I would appreciate guidance of how to refactor it and what to look for in terms of efficiency?

Optimisation I'd like to achieve would be, less type conversion, no zero items in the list, would there be a better way to find the max number in a list, or .Sort(); is good enough? 

Any ideas welcome, thank you.

using System;
using System.Collections.Generic;

namespace rec
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine(FindGap(777)); // 
        }

        public static int FindGap(int number)
        {
            string toBinary = Convert.ToString(number, 2);

            char[] toChar = toBinary.ToCharArray();

            string previous = "";
            string current = "";
            int count = 0;
            int answer = 0;
            List&lt;int&gt; lastGap = new List&lt;int&gt;();

            for (int i = 0; i &lt; toChar.Length; i++)
            {
                if (toChar[i].ToString() == "1")
                {
                    // temp becomes 1
                    current = toChar[i].ToString();

                    if (current == "1")
                    {
                        lastGap.Add(count);
                        count = 0;
                        continue;
                    }
                }
                if (toChar[i].ToString() == "0" &amp;&amp; current == "1")
                {
                    current = "0";

                    count++;

                    previous = current;
                }
                else if (toChar[i].ToString() == "0" &amp;&amp; previous == "0")
                {
                    current = "0";
                    count++;
                    previous = current;
                }
            }
            lastGap.Sort();
            answer = lastGap.Last();

            if (answer &gt; 1)
            {
                return answer;
            }
            else return 0;
        }
    }
}
If you're just looking for the longest stretch of zeros you don't need to use a list at all. You just iterate through the binary representation until you find a stretch of zeros. If you hit a new high score, you can overwrite the old high score with the new one and keep moving forward, forgetting about the past.

This is called a "greedy algorithm."

    public static int FindGap(int number)
    {
        string binaryRep = Convert.ToString(number, 2);

        int maxGapSize = 0;
        int currGapSize = 0;

        foreach(char ch in binaryRep)
        {
            if (ch == '0')
            {
                currGapSize++;
            }
            else
            {
                maxGapSize = Math.Max(currGapSize, maxGapSize);
                currGapSize = 0;
            }
        }

        return maxGapSize;
    }


If you want to get really fancy, you don't even need to convert the number to a string. You can use bit shifts to "iterate" through the bits in the number. The number 9 is 1001 in binary. Shift the bits over one, and you've got 100. Shift it over again, and you've got 10. You can use modulus operations to see if the least significant digit is 0 or 1. 

This is just a fancy way to repeatedly divide by 2. In fact, you could solve this problem by dividing by 2 instead but this way works as well. (There's also probably a more terse way to write this, but this is perfectly efficient.)

    public static int FindGap2(int number)
    {
        int maxGapSize = 0;
        int currGapSize = 0;

        if (number == 0)
            return 0;

        while (number % 2 == 0)
            number = number &gt;&gt; 1;

        while (number &gt; 0)
        {
            if(number%2 == 0)
            {
                currGapSize++;
            }
            else
            {
                maxGapSize = Math.Max(currGapSize, maxGapSize);
                currGapSize = 0;
            }
            number = number &gt;&gt; 1;
        }

        return maxGapSize;
    }